#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
const int nmax=100005;
map<int,int> norm;
vector<int> v[nmax];
vector< pair<int,int> > l[nmax];
pair<int,int> vv[2*nmax];
long long aib[nmax];
int p[nmax],w[nmax],tt[nmax],lev[nmax],c[nmax],a[nmax],b[nmax],x[nmax];
int n,i,j,paths,nr,in,val;
long long ans;
void dfs(int x)
{
int nod,big=0;
w[x]=1;
for(int i=0;i<v[x].size();i++)
{
nod=v[x][i];lev[nod]=lev[x]+1;
dfs(nod);
w[x]+=w[nod];
if(w[nod]>w[big])
big=nod;
}
if(!big) p[x]=++paths;
else p[x]=p[big];
for(int i=0;i<v[x].size();i++)
if(v[x][i]!=big)
{
tt[p[v[x][i]]]=x;
}
}
int get(int wh,int x)
{
int ret=0;
for(int p=16;p>=0;p--)
if(ret+(1<<p)<l[wh].size()&&lev[l[wh][ret+(1<<p)].first]>=lev[x])
ret+=(1<<p);
ret++;
return ret;
}
inline int lbit(int x)
{
return ((x^(x-1))&x);
}
void update(int poz,long long val)
{
for(int idx=poz;idx<=n;idx+=lbit(idx))
aib[idx]+=val;
}
long long compute(int poz)
{
long long ret=0;
for(int idx=poz;idx>0;idx-=lbit(idx))
ret+=1LL*aib[idx];
return ret;
}
void ffffffffft(int x)
{
int wh;
nr=0;
while(x!=0)
{
in=get(p[x],x);
wh=p[x];
vv[++nr]={lev[x],l[wh][in-1].second};
for(i=in;i<l[wh].size();i++)
vv[++nr]={lev[l[wh][i].first],l[wh][i].second};
x=tt[p[x]];
}
vv[nr+1]={0,0};
ans=0;
for(val=1;val>=-1;val-=2)
{
for(i=1;i<=nr;i++)
{
update(vv[i].second,(vv[i].first-vv[i+1].first)*val);
if(val==1)
ans+=1LL*compute(vv[i].second-1)*(vv[i].first-vv[i+1].first);
}
}
}
void nttttttttt(int x,int col)
{
int wh;
while(x!=0)
{
wh=p[x];
while(l[wh].size()&&lev[l[wh].back().first]<=lev[x])
l[wh].pop_back();
l[wh].push_back({x,col});
x=tt[p[x]];
}
}
int main()
{
//freopen("data.in","r",stdin);
ios_base::sync_with_stdio(false);
cin>>n;
for(i=1;i<=n;i++)
cin>>c[i],x[i]=c[i];
sort(x+1,x+n+1);
for(i=1;i<=n;i++)
norm[x[i]]=i;
for(i=1;i<=n;i++)
c[i]=norm[c[i]];
for(i=1;i<=n-1;i++)
{
cin>>a[i]>>b[i];
v[a[i]].push_back(b[i]);
}
lev[1]=1;
dfs(1);
l[p[1]].push_back({1,c[1]});
for(int cnt=1;cnt<=n-1;cnt++)
{
ffffffffft(a[cnt]);
nttttttttt(b[cnt],c[b[cnt]]);
cout<<ans<<'\n';
}
return 0;
}
