//1L1YA
#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3,unrool-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
#define Pb push_back
#define F first
#define S second
#define endl '\n'
#define sep ' '
#define all(x) x.begin(),x.end()
#define al(x,n) x+1,x+n+1
#define SZ(x) ((int)x.size())
#define lc (id<<1)
#define rc (lc|1)
#define mid (l+r>>1)
#define dokme(x) cout << x << endl, exit(0)
#define sik(x) cout << x << endl;continue;
#define FastIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define FileIO freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll oo=1e18;
const int mod=1e9+7;
const int inf=1e9+111;
const int N=1e5+11;
const int lg=19;
int n,t=1,a[N],h[N],sz[N],st[N],up[N],fen[N],head[N],seg[N<<2],par[lg][N];
vector<int> G[N];
vector<pii> E(N);
void shift(int id){
if(!seg[id]) return;
seg[lc]=seg[id];seg[rc]=seg[id];
seg[id]=0;
}
void update(int ql,int qr,int val,int id=1,int l=1,int r=n+1){
if(qr<=l || ql>=r) return;
if(ql<=l && r<=qr){
seg[id]=val;
return;
}
shift(id);
update(ql,qr,val,lc,l,mid);
update(ql,qr,val,rc,mid,r);
}
int get(int pos,int id=1,int l=1,int r=n+1){
if(r-l==1) return seg[id];
shift(id);
if(pos<mid) return get(pos,lc,l,mid);
return get(pos,rc,mid,r);
}
bool cmp(int x,int y){
return sz[x]>sz[y];
}
void dfsset(int v){
sz[v]=1;
for(int u: G[v]){
h[u]=h[v]+1;
dfsset(u);
sz[v]+=sz[u];
}
sort(all(G[v]),cmp);
}
void dfs_hld(int v){
st[v]=t++;
if(SZ(G[v])) head[G[v][0]]=head[v];
for(int u: G[v]) dfs_hld(u);
}
void update_path(int v,int x){
while(head[v]!=1){
update(st[head[v]],st[v]+1,x);
v=par[0][head[v]];
}
update(1,st[v]+1,x);
}
int jump(int v,int k){
if(k<0) return v;
for(int i=0;i<lg;i++)
if(k>>i & 1)
v=par[i][v];
return v;
}
void upd(int x,int y){
for(x=n-x;x<=n;x+=x&-x) fen[x]+=y;
}
int gett(int x){
int ans=0;
for(x=n-x;x;x-=x&-x) ans+=fen[x];
return ans;
}
int main(){
FastIO
cin >> n;
vector<int> comp;
for(int i=1;i<=n;i++) cin >> a[i],comp.Pb(a[i]);
sort(all(comp));
comp.resize(unique(all(comp))-comp.begin());
for(int i=1;i<=n;i++) a[i]=lower_bound(all(comp),a[i])-comp.begin();
for(int i=1;i<n;i++){
int u,v;
cin >> u >> v;
par[0][v]=u;
G[u].Pb(v);
E[i]={u,v};
}
for(int i=1;i<lg;i++)
for(int v=1;v<=n;v++)
par[i][v]=par[i-1][par[i-1][v]];
dfsset(1);
for(int i=1;i<=n;i++) head[i]=i;
dfs_hld(1);
update_path(1,1);
up[1]=1;
for(int i=1;i<n;i++){
int u=E[i].F,v=E[i].S;
vector<pii> vc;
while(u){
int w=get(st[u]);
vc.Pb({w,h[u]-h[up[w]]+1});
int p=jump(w,h[w]-h[u]-1);
u=par[0][up[w]];
up[w]=p;
}
reverse(all(vc));
ll ans=0;
for(auto [x,y]: vc) ans+=(ll)y*gett(a[x]+1),upd(a[x],y);
cout << ans << endl;
for(auto [x,y]: vc) upd(a[x],-y);
up[v]=1;
update_path(v,v);
}
return 0;
}
