#include<bits/stdc++.h>
#define ll int
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
#define sz(a) ((ll)(a).size())
using namespace std;
const ll maxn=100005;
vector <pll> edges;
vector <ll> A[maxn];
ll a[maxn], h[maxn], dep[maxn];
ll Time, tin[maxn], tout[maxn], pa[maxn];
void dfs(ll u)
{
tin[u]=++Time;
for (ll v:A[u])
if (v!=pa[u])
dep[v]=dep[u]+1, pa[v]=u, dfs(v);
tout[u]=Time;
}
namespace SegTree
{
ll n;
pll St[maxn*4];
void init(ll sz){n=sz;}
void update(ll i, ll Start, ll End, ll idx, pll v)
{
if (Start==End) {St[i]=v; return;}
ll mid=(Start+End)/2;
if (mid>=idx) update(i*2, Start, mid, idx, v);
else update(i*2+1, mid+1, End, idx, v);
St[i]=max(St[i*2], St[i*2+1]);
}
void update(ll idx, pll v) {update(1, 1, n, idx, v);}
pll query(ll i, ll Start, ll End, ll l, ll r)
{
if (Start>r || End<l) return {0, 0};
if (Start>=l && End<=r) return St[i];
ll mid=(Start+End)/2;
if (mid<l) return query(i*2+1, mid+1, End, l, r);
if (mid+1>r) return query(i*2, Start, mid, l, r);
return max(query(i*2, Start, mid, l, r), query(i*2+1, mid+1, End, l, r));
}
pll query(ll l, ll r){return query(1, 1, n, l, r);}
}
struct BIT
{
ll n;
vector <ll> bit;
BIT (ll n): n(n){bit.assign(n+1, 0);}
void update(ll i, ll val)
{
for (; i<=n; i+=i&(-i))
bit[i]+=val;
}
ll query(ll l, ll r)
{
ll ans=0; l--;
for (; r; r-=r&(-r)) ans+=bit[r];
for (; l; l-=l&(-l)) ans-=bit[l];
return ans;
}
};
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll n; cin >> n; SegTree::init(n);
for (ll i=1; i<=n; i++) cin >> a[i], h[i]=1;
edges.resize(n-1);
for (auto &[u, v]:edges)
cin >> u >> v, A[u].pb(v), A[v].pb(u);
dfs(1), SegTree::update(tin[1], {0, 1}), h[1]=1;
for (ll i=1; i<=n; i++)
{
for (ll &j:A[i]) if (j==pa[i])
{swap(j, A[i].back()), A[i].pop_back(); break;}
sort(A[i].begin(), A[i].end(), [&](ll a, ll b){return tin[a]<tin[b];});
}
for (ll i=0; i<sz(edges); i++)
{
ll U=edges[i].fi, V=edges[i].se, crr=U;
vector <ll> v;
vector <pll> num;
while (crr)
{
ll x=SegTree::query(tin[crr], tout[crr]).se, top=h[x];
if (x!=crr)
{
ll p=upper_bound(A[crr].begin(), A[crr].end(), x, [&](ll a, ll b){return tin[a]<tin[b];})-A[crr].begin();
h[x]=A[crr][p-1];
}
num.pb({dep[crr]-dep[top]+1, a[x]}), v.pb(a[x]), crr=pa[top];
}
SegTree::update(tin[V], {i+1, V});
sort(v.begin(), v.end());
v.resize(unique(v.begin(), v.end())-v.begin());
ll k=sz(v), ans=0;
BIT B(k);
for (auto [cnt, x]:num)
{
x=lower_bound(v.begin(), v.end(), x)-v.begin()+1;
ans+=B.query(1, x-1)*cnt, B.update(x, cnt);
}
cout << ans << "\n";
}
}
