#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=1e5+50;
const ll mod=1e9+7;
using namespace std;
int x,y,i,n,up[nmax][20],tin[nmax],tout[nmax],tt,ex[nmax],ey[nmax],c[nmax],d,z,u,j,lvl[nmax],sz,nr,lc,fw[nmax];
ll rs;
vector<int>a[nmax];
pair<int,int>st[4*nmax],pr;
vector<int>vc;
vector<pair<int,int> >vec;
void ufw(int i,int v)
{
for(;i>=1;i-=i&(-i))fw[i]+=v;
}
int qfw(int i)
{
int ans=0;
for(;i<=sz;i+=i&(-i))ans+=fw[i];
return ans;
}
void dfs(int x,int p)
{
lvl[x]=lvl[p]+1;
tin[x]=++tt;
up[x][0]=p;
for(int i=1;i<17;i++)up[x][i]=up[up[x][i-1]][i-1];
for(int i=0;i<(int)a[x].size();i++)dfs(a[x][i],x);
tout[x]=tt;
}
int anc(int x,int y)
{
return tin[x]<=tin[y] && tout[x]>=tout[y];
}
int lca(int x,int y)
{
if(anc(x,y))return x;
if(anc(y,x))return y;
for(int i=16;i>=0;i--)if(!anc(up[x][i],y))x=up[x][i];
return up[x][0];
}
void upd(int nod,int l,int r,int p,pair<int,int>v)
{
if(l==r)
{
st[nod]=v;
return;
}
int mid=(l+r)/2;
if(p<=mid)upd(2*nod,l,mid,p,v);
else upd(2*nod+1,mid+1,r,p,v);
st[nod]=max(st[2*nod],st[2*nod+1]);
}
pair<int,int> qry(int nod,int l,int r,int tl,int tr)
{
if(tr<l || tl>r)return mkp(0,0);
if(tl<=l && r<=tr)return st[nod];
int mid=(l+r)/2;
return max(qry(2*nod,l,mid,tl,tr),qry(2*nod+1,mid+1,r,tl,tr));
}
int main()
{
//freopen("sol.in","r",stdin);
//freopen("sol.out","w",stdout);
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
cin>>n;
for(i=1;i<=n;i++)cin>>c[i],vc.pb(c[i]);
sort(all(vc));
vc.resize(unique(all(vc))-vc.begin());
sz=(int)vc.size();
for(i=1;i<=n;i++)c[i]=lower_bound(all(vc),c[i])-vc.begin()+1;
for(i=1;i<n;i++)
{
cin>>ex[i]>>ey[i];
a[ex[i]].pb(ey[i]);
}
dfs(1,1);
for(i=1;i<n;i++)
{
x=ex[i],y=ey[i];
vec.clear();
z=1,rs=0;
while(1)
{
pr=qry(1,1,n,tin[z],tout[z]);
if(!pr.fr)break;
u=pr.sc;
lc=lca(y,u);
nr=qfw(c[u]+1);
rs+=1LL*nr*1LL*(lvl[lc]-lvl[z]+1);
ufw(c[u],lvl[lc]-lvl[z]+1);
vec.pb(mkp(c[u],lvl[lc]-lvl[z]+1));
if(lc==x)break;
d=lvl[y]-lvl[lc]-1;
z=y;
for(j=16;j>=0;j--)if(d&(1<<j))z=up[z][j];
}
upd(1,1,n,tin[y],mkp(i,y));
for(j=0;j<(int)vec.size();j++)ufw(vec[j].fr,-vec[j].sc);
cout<<rs<<'\n';
}
return 0;
}
