#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
const int N=1e5+99;
int n,t,col[N],sz[N],up[N],X[N],Y[N],h[N],par[N];
ll fenwik[N];
vector<int> g[N];
vector<pair<int,int> > res,v[N];
void add(int x, int val){ for(x++;x<N;x+=x&-x) fenwik[x]+=val; }
ll get(int x) { ll res=0; for (x++;x>0;x-=x&-x) res+=fenwik[x]; return res; }
void dfs1(int u){
int x=-1;
sz[u]=1;
f(i,0,g[u].size()){
int v=g[u][i];
dfs1(v);
sz[u]+=sz[v];
if(x==-1 || sz[v]>sz[g[u][x]]){
x=i;
}
}
if(x!=-1){
swap(g[u][0],g[u][x]);
}
}
void dfs2(int u){
int t=1;
for(auto v : g[u]){
h[v]=h[u]+1;
if(t){
up[v]=up[u];
}
else{
up[v]=v;
}
dfs2(v);
t=0;
}
v[up[u]].pb({col[u],1});
}
void del(int u,int x,int c){
vector<pair<int,int> > vec;
int t=x;
while(t>0){
int p=min(t,v[u].back().S);
v[u].back().S-=p;
t-=p;
vec.pb({v[u].back().F,p});
if(v[u].back().S>0 || t==0) break;
v[u].pop_back();
}
v[u].pb({c,x});
reverse(all(vec));
for(auto p : vec){
res.pb(p);
}
}
void query(int u,int c){
while(u>0){
del(up[u],h[u]-h[up[u]]+1,c);
u=par[up[u]];
}
}
void get_ans(){
ll ans=0;
res[0].S--;
for(auto p : res){
add(p.F,p.S);
ans+=get(p.F-1)*p.S;
}
for(auto p : res){
add(p.F,-p.S);
}
res.clear();
cout<<ans<<endl;
}
int main(){
vector<int> vec;
cin>>n;
f(i,1,n+1){
cin>>col[i];
vec.pb(col[i]);
}
sort(all(vec));
f(i,1,n+1){
col[i]=lower_bound(all(vec),col[i])-vec.begin()+1;
}
f(i,1,n){
cin>>X[i]>>Y[i];
par[Y[i]]=X[i];
g[X[i]].pb(Y[i]);
}
up[1]=1;
dfs1(1);
dfs2(1);
f(i,1,n){
query(Y[i],col[Y[i]]);
get_ans();
}
}
