/* in the name of allah */
#include<bits/stdc++.h>
using namespace std;
//#define endl '\n'
#define pb push_back
#define F first
#define S second
#define mk make_pair
#define lc (2*id)
#define rc (2*id+1)
#define md ((s+e)/2)
#define ln (e-s+1)
typedef long long ll;
const int N=1e5+7,lg=20;
int n,c[N],a[N],b[N],h[N],p[N],fen[N],sp[N][lg],x;
int seg[4*N],st[N],fn[N],T;
pair<int,int>com[N];
ll ans[N];
vector<int>vec[N];
vector<pair<int,int>>vc;
void upd(int i,int x){
for(;i<N;i+=i&(-i)){
fen[i]+=x;
}
}
int get(int i){
int ans=0;
for(;i;i-=i&(-i)){
ans+=fen[i];
}
return ans;
}
void upds(int k,int x,int id=1,int s=1,int e=n){
if(ln==1){
seg[id]=x;
return;
}
if(k<=md) upds(k,x,lc,s,md);
else upds(k,x,rc,md+1,e);
seg[id]=max(seg[lc],seg[rc]);
}
int gets(int l,int r,int id=1,int s=1,int e=n){
if(l>e || s>r){
return 0;
}
if(s>=l && e<=r){
return seg[id];
}
return max(gets(l,r,lc,s,md),gets(l,r,rc,md+1,e));
}
int lca(int u,int v){
for(int i=lg-1;i>=0;i--){
if(h[sp[u][i]]>=h[v]){
u=sp[u][i];
}
if(h[sp[v][i]]>=h[u]){
v=sp[v][i];
}
}
for(int i=lg-1;i>=0;i--){
if(sp[u][i]!=sp[v][i]){
u=sp[u][i];
v=sp[v][i];
}
}
return u;
}
void dfs(int v=1){
st[v]=++T;
for(auto u:vec[v]){
dfs(u);
}
fn[v]=T;
}
int main(){
ios:: sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>c[i];
com[i]=mk(c[i],i);
}
int k=1;
sort(com,com+n+1);
for(int i=1;i<=n;i++){
c[com[i].S]=k;
if(com[i].F!=com[i+1].F)k++;
}
for(int i=0;i<n-1;i++){
cin>>a[i]>>b[i];
p[b[i]]=a[i];
h[b[i]]=h[a[i]]+1;
sp[b[i]][0]=a[i];
vec[a[i]].pb(b[i]);
}
dfs();
for(int j=1;j<lg;j++){
for(int i=1;i<=n;i++){
sp[i][j]=sp[sp[i][j-1]][j-1];
}
}
upds(1,1);
b[-1]=1;
for(int i=0;i<n-1;i++){
int u=1;
vc.clear();
while(u!=b[i]){
int v;
int x=b[gets(st[u],fn[u])-2];
//cout<<u<<endl;
if(u==a[i])v=b[i];
else v=lca(a[i],x);
ll t=h[v]-h[u];
ans[i]+=t*(get(N-1)-get(c[x]));
upd(c[x],t);
vc.pb(mk(c[x],t));
u=v;
}
for(auto [p,q]:vc){
upd(p,-q);
}
upds(st[b[i]],i+2);
cout<<ans[i]<<endl;
}
}
