#include <bits/stdc++.h>
#define DEBUG 1
using namespace std;
namespace output{
void __(short x){cout<<x;}
void __(unsigned x){cout<<x;}
void __(int x){cout<<x;}
void __(long long x){cout<<x;}
void __(unsigned long long x){cout<<x;}
void __(double x){cout<<x;}
void __(long double x){cout<<x;}
void __(char x){cout<<x;}
void __(const char*x){cout<<x;}
void __(const string&x){cout<<x;}
void __(bool x){cout<<(x?"true":"false");}
template<class S,class T>
void __(const pair<S,T>&x){__(DEBUG?"(":""),__(x.first),__(DEBUG?", ":" "),__(x.second),__(DEBUG?")":"");}
template<class T>
void __(const vector<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
template<class T>
void __(const set<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
template<class T>
void __(const multiset<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
template<class S,class T>
void __(const map<S,T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
void pr(){cout<<"\n";}
template<class S,class... T>
void pr(const S&a,const T&...b){__(a);if(sizeof...(b))__(' ');pr(b...);}
}
using namespace output;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,char> pic;
typedef pair<double,double> pdd;
typedef pair<ld,ld> pld;
typedef vector<int> vi;
typedef vector<ll> vl;
#define pb push_back
#define fox(i,x,y) for(int i=(x);i<=(y);i++)
#define foxr(i,x,y) for(int i=(y);i>=(x);i--)
struct Treap{
struct nd{
int p, sz, sm, k; nd *l, *r;
nd(int key,int size):p(rand()),sz(size),sm(size),k(key),l(0),r(0){}
}*rt=NULL,*l,*r,*t;
void clear(){
rt=l=r=t=NULL;
}
inline int sz(nd *n){return n?n->sz:0;}
inline int sm(nd *n){return n?n->sm:0;}
inline void upd(nd *&n){
if(!n) return;
n->sm=sm(n->l)+sm(n->r)+sz(n);
}
void split(nd *n,nd *&l,nd *&r,int k){
if(!n) l=r=NULL;
else if(n->k<=k) split(n->r,n->r,r,k),l=n;
else split(n->l,l,n->l,k),r=n;
upd(n);
}
void mrg(nd *&n,nd *l,nd *r){
if(!l||!r) n=l?l:r;
else if(l->p>r->p) mrg(l->r,l->r,r),n=l;
else mrg(r->l,l,r->l),n=r;
upd(n);
}
ll insert(int key,int size){
split(rt,l,r,key);
split(l,l,t,key-1);
ll ret = 1LL*size*sm(l);
if(!t) t=new nd(key,size);
else t->sz+=size,t->sm+=size;
mrg(l,l,t);
mrg(rt,l,r);
return ret;
}
}treap;
const int MN = 1e5+5;
ll N, c[MN], i, x, y, id[MN], sz[MN], len[MN], par[MN], lnk[MN], nxt, stid, pos[MN];
struct idk{ll st, ed, val;};
stack<idk> hld[MN];
vl adj[MN]; pll ed[MN], big[MN];
void dfs(ll n){
sz[n] = 1;
big[n]={-1,-1};
for(auto v : adj[n]){
par[v] = n;
dfs(v);
sz[n] += sz[v];
if(sz[v]>big[n].first)
big[n]={sz[v],v};
}
if(big[n].second!=-1) len[n]=1+len[big[n].second];
}
void dfs2(ll n){
if(!lnk[n]){
lnk[n]=n; pos[n]=++nxt; nxt+=len[n];
id[n]=++stid;
}
else{
pos[n]=pos[par[n]]+1;
id[n]=id[par[n]];
}
for(auto v : adj[n]){
if(v==big[n].second) lnk[v] = lnk[n];
dfs2(v);
}
}
int main(){
srand(time(0));
for(scanf("%lld",&N),i=1;i<=N;i++)
scanf("%lld",&c[i]);
for(i=1;i<N;i++){
scanf("%lld%lld",&x,&y);
adj[x].pb(y);
ed[i]={x,y};
}
dfs(1); dfs2(1);
hld[id[1]].push({pos[1],pos[1],c[1]});
for(i=1;i<N;i++){
treap.clear();
ll ans = 0, cur = ed[i].second, rep, st, tmp, col=c[ed[i].second];
vector<pll> blk;
while(cur){
rep = lnk[cur]; blk.clear();
st = id[rep];
while(hld[st].size()){
if(hld[st].top().ed<=pos[cur]){
blk.pb({hld[st].top().ed-hld[st].top().st+1,hld[st].top().val});
hld[st].pop();
}
else{
blk.pb({pos[cur]-hld[st].top().st+1,hld[st].top().val});
tmp=hld[st].top().ed; hld[st].pop();
hld[st].push({pos[cur]+1,tmp,blk.back().second});
break;
}
}
hld[st].push({pos[rep],pos[cur],col});
reverse(blk.begin(),blk.end());
for(auto v : blk){
ans += treap.insert(v.second,v.first);
}
cur = par[rep];
}
printf("%lld\n",ans);
}
return 0;
}
