#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int inf=1e9+7;
int n,a[100005],aa[100005],b[100005],c[100005],dp[100005],ind[100005],orig[100005],br,lazy[400005],lead[100005],up[100005],p[400005],mi[400005],ma[400005],le;
vector<int>v[100005];
map<int,int>m;
void make_dp(int beg,int par)
{
int w;
dp[beg]=1;
up[beg]=par;
for(int i=0;i<v[beg].size();i++)
{
w=v[beg][i];
if(w!=par)
{
make_dp(w,beg);
dp[beg]+=dp[w];
}
}
}
void make_ind(int beg,int par,int l)
{
br++;
ind[beg]=br;
orig[br]=beg;
lead[beg]=l;
int w,ma=0,to=0;
for(int i=0;i<v[beg].size();i++)
{
w=v[beg][i];
if(w!=par)
{
if(ma<dp[w])
{
ma=dp[w];
to=w;
}
}
}
if(to)make_ind(to,beg,l);
for(int i=0;i<v[beg].size();i++)
{
w=v[beg][i];
if(w!=par&&w!=to)
{
make_ind(w,beg,w);
}
}
}
void prec()
{
for(int i=1;i<=n*4;i++)
{
mi[i]=inf;
}
for(int i=1;i<=n;i++)
{
aa[i]=a[i];
}
sort(aa+1,aa+n+1);
int num=1;
for(int i=1;i<=n;i++)
{
if(aa[i]!=aa[i+1])
{
m[aa[i]]=num;
num++;
}
}
for(int i=1;i<=n;i++)
{
a[i]=m[a[i]];
}
}
void h_update(int l,int r,int q,int h,int st)
{
if(l>q||r<q)return;
if(l==r)
{
p[h]+=st;
return;
}
int mid=(l+r)/2;
h_update(l,mid,q,h*2,st);
h_update(mid+1,r,q,h*2+1,st);
p[h]=p[h*2]+p[h*2+1];
}
int h_query(int l,int r,int ql,int qr,int h)
{
if(l>qr||r<ql)return 0;
if(l>=ql&&r<=qr)return p[h];
int mid=(l+r)/2;
return h_query(l,mid,ql,qr,h*2)+h_query(mid+1,r,ql,qr,h*2+1);
}
void h_clear(int l,int r,int h)
{
if(l==r)
{
p[h]=0;
return;
}
int mid=(l+r)/2;
if(p[h*2])h_clear(l,mid,h*2);
if(p[h*2+1])h_clear(mid+1,r,h*2+1);
p[h]=0;
}
void push_lazy(int h)
{
if(lazy[h])
{
mi[h]=lazy[h];
ma[h]=lazy[h];
lazy[h*2]=lazy[h];
lazy[h*2+1]=lazy[h];
lazy[h]=0;
}
}
void check(int l,int r,int h)
{
push_lazy(h);
cout<<l<<" "<<r<<" "<<mi[h]<<" "<<ma[h]<<" "<<h<<endl;
if(l==r)return;
int mid=(l+r)/2;
check(l,mid,h*2);
check(mid+1,r,h*2+1);
mi[h]=min(mi[h*2],mi[h*2+1]);
ma[h]=max(ma[h*2],ma[h*2+1]);
}
void update(int l,int r,int ql,int qr,int h,int st)
{
if(l>qr||r<ql)return;
if(l>=ql&&r<=qr)
{
lazy[h]=st;
push_lazy(h);
//cout<<l<<" "<<r<<" "<<lazy[h]<<" "<<mi[h]<<" "<<h<<" ! "<<endl;
//if(mi[h]==4)check(1,n,1);
return;
}
push_lazy(h);
int mid=(l+r)/2;
update(l,mid,ql,qr,h*2,st);
update(mid+1,r,ql,qr,h*2+1,st);
mi[h]=min(mi[h*2],mi[h*2+1]);
ma[h]=max(ma[h*2],ma[h*2+1]);
}
int get_value(int l,int r,int q,int h)
{
if(l>q||r<q)return 0;
push_lazy(h);
if(l==r)return mi[h];
int mid=(l+r)/2;
return max(get_value(l,mid,q,h*2),get_value(mid+1,r,q,h*2+1));
}
void query(int l,int r,int ql,int qr,int h,int val)
{
//cout<<l<<" "<<r<<" "<<mi[h]<<" "<<ma[h]<<" "<<ql<<" "<<qr<<endl;
push_lazy(h);
if(l==r)
{
if(mi[h]==val)
{
//cout<<val<<" "<<mi[l]<<endl;
le=l;
}
return;
}
push_lazy(h*2);
push_lazy(h*2+1);
int mid=(l+r)/2;
//cout<<mi[h*2+1]<<" "<<val<<" "<<mid+1<<endl;
if(mid<ql||((mi[h*2+1]!=val||ma[h*2+1]!=val)&&mid+1<=qr))
{
//cout<<"!!!!"<<endl;
query(mid+1,r,ql,qr,h*2+1,val);
}
else
{
le=mid+1;
query(l,mid,ql,qr,h*2,val);
}
}
void get_otg(int start)
{
int cur=start,top,br=0,old,val,nv;
val=get_value(1,n,ind[cur],1);
long long int otg=0;
//cout<<start<<endl;
while(true)
{
top=lead[cur];
old=cur;
le=ind[cur];
query(1,n,ind[top],ind[cur],1,val);
//cout<<le<<endl;
cur=orig[le];
//cout<<endl;
//check(1,n,1);
//cout<<endl;
br+=ind[old]-ind[cur]+1;
//cout<<cur<<" "<<br<<" "<<val<<" "<<top<<endl;
nv=get_value(1,n,ind[up[cur]],1);
if(cur==1||val!=nv)
{
otg+=br*h_query(1,n,1,val-1,1);
h_update(1,n,val,1,br);
val=nv;
br=0;
if(cur==1)break;
}
cur=up[cur];
}
//cout<<endl<<endl;
cout<<otg<<endl;
}
void fix_tree(int cur,int st)
{
h_clear(1,n,1);
int top;
while(cur!=0)
{
top=lead[cur];
update(1,n,ind[top],ind[cur],1,st);
//check(1,n,1);
//cout<<endl<<endl;
cur=up[top];
if(cur==0)return;
}
}
void read()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<n;i++)
{
cin>>b[i]>>c[i];
v[b[i]].push_back(c[i]);
v[c[i]].push_back(b[i]);
}
prec();
make_dp(1,0);
make_ind(1,0,1);
update(1,n,1,1,1,a[1]);
//check(1,n,1);
for(int i=1;i<n;i++)
{
get_otg(b[i]);
fix_tree(c[i],a[c[i]]);
//cout<<endl<<endl;
//check(1,n,1);
}
}
int main()
{
speed();
read();
return 0;
}
