// Code by Parsa Eslami
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define all(x) x.begin(),x.end()
#define SZ(x) ((int)x.size())
#define bit(i,j) ((j>>i)&1)
#define pb push_back
#define lc 2*id
#define rc 2*id+1
#define dmid int mid=(r+l)/2
#define err(x) cerr<#x<<" : "<<x<<'\n'
#define F first
#define S second
using namespace std;
const int N=1e5+4;
const int lg=20;
vector<int> adj[N];
int val[N];
int h[N],par[lg][N],st[N],en[N],tme;
int ver[N];
int seg[4*N];
int n;
struct fenwick{
int fen[N];
void add(int k,int x){
while(k>0){
fen[k]+=x;
k-=(k&(-k));
}
}
int get(int k){
int rt=0;
while(k<N){
rt+=fen[k];
k+=(k&(-k));
}
return rt;
}
};
fenwick fen;
int Get(){
int x; cin>>x; return x;
}
int PAR(int v,int k){
while(k>0){
v=par[__builtin_ctz(k)][v];
k-=(k&(-k));
}
return v;
}
int LCA(int u,int v){
if(h[u]<h[v]) swap(u,v);
u=PAR(u,h[u]-h[v]);
if(u==v) return u;
FORR(j,lg-1,0) if(par[j][u]!=par[j][v]){
u=par[j][u];
v=par[j][v];
}
return par[0][v];
}
void upd(int id,int l,int r,int ind,int x){
if(ind<l||ind>=r) return;
seg[id]=x;
if(l+1==r) return;
dmid;
upd(lc,l,mid,ind,x);
upd(rc,mid,r,ind,x);
}
int get(int id,int l,int r,int s,int e){
if(s>=r||e<=l) return 0;
if(s<=l&&e>=r) return seg[id];
dmid;
return max(get(lc,l,mid,s,e),get(rc,mid,r,s,e));
}
ll GET(int u){
vector<pii> vc;
int root=1;
while(1){
int w=ver[get(1,1,n+1,st[root],en[root]+1)];
int y=val[w];
w=LCA(u,w);
vc.pb({y,h[w]-h[root]+1});
if(w==u) break;
root=PAR(u,h[u]-h[w]-1);
}
//for(pii x:vc) cout<<x.F<<"."<<x.S<<" ";
//cout<<'\n';
ll rt=0;
for(pii x:vc){
rt+=fen.get(x.F+1)*x.S;
fen.add(x.F,x.S);
}
for(pii x:vc) fen.add(x.F,-x.S);
return rt;
}
void dfs(int v){
st[v]=++tme;
for(int u:adj[v]) dfs(u);
en[v]=tme;
}
int32_t main(){
iostream::sync_with_stdio(0); cin.tie(0);
n=Get();
FOR(i,1,n) val[i]=Get();
vector<pii> vc;
FOR(i,1,n) vc.pb({val[i],i});
sort(all(vc)); int x0=0;
FOR(i,0,SZ(vc)-1){
if(i==0||vc[i].F!=vc[i-1].F) x0++;
val[vc[i].S]=x0;
}
int U[n],V[n];
FOR(i,1,n-1){
U[i]=Get(); V[i]=Get();
int u=U[i],v=V[i];
adj[u].pb(v);
par[0][v]=u;
h[v]=h[u]+1;
}
FOR(j,1,lg-1) FOR(i,1,n) par[j][i]=par[j-1][par[j-1][i]];
dfs(1);
upd(1,1,n+1,st[1],1); ver[1]=1;
FOR(i,1,n-1){
cout<<GET(U[i])<<'\n';
upd(1,1,n+1,st[V[i]],i+1); ver[i+1]=V[i];
}
return 0;
}
