#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<ll>::iterator sit;
typedef map<ll,ll>::iterator mit;
int a[111111];
int sz[111111];
int in[111111];
int rin[111111];
int t;
int out[111111];
deque<ii> chain[111111]; //heavy chain starting at vertex u
int nxt[111111];
vi adj[111111];
int par[111111];
int h[111111];
void addtochain(int u, int v)
{
if(chain[u].empty()) chain[u].pb(mp(v,1));
else if(chain[u].back().fi==v) chain[u].back().se++;
else chain[u].pb(mp(v,1));
}
void dfs_sz(int v = 0)
{
sz[v] = 1;
for(auto &u: adj[v])
{
par[u] = v; h[u] = h[v] + 1;
dfs_sz(u);
sz[v] += sz[u];
if(sz[u] > sz[adj[v][0]])
swap(u, adj[v][0]);
}
}
void dfs_hld(int v = 0)
{
in[v] = t++;
rin[in[v]] = v;
for(auto u: adj[v])
{
nxt[u] = (u == adj[v][0] ? nxt[v] : u);
dfs_hld(u);
}
out[v] = t;
}
int fen[111111];
int N;
void init(int n)
{
N=n;
for(int i=0;i<=N;i++) fen[i]=0;
}
void update(int pos, int v)
{
pos++;
for(;pos<=N;pos+=(pos&(-pos)))
{
fen[pos]+=v;
}
}
int query(int pos)
{
pos++;
int sum=0;
for(;pos;pos-=(pos&(-pos)))
{
sum+=fen[pos];
}
return sum;
}
ll calc_path(int u)
{
vector<ii> V; vi coord;
while(u!=-1)
{
int nu = nxt[u];
int siz = h[u] - h[nu] + 1;
vector<ii> tst;
//cerr<<"CHAIN : "<<u<<' '<<nu<<'\n';
for(int i=0;i<chain[nu].size();i++)
{
int cnt = chain[nu][i].fi; int v = chain[nu][i].se;
if(cnt<=siz)
{
tst.pb(mp(cnt,v));
siz-=cnt;
}
else
{
tst.pb(mp(siz,v));
break;
}
}
for(int i=int(tst.size())-1;i>=0;i--)
{
V.pb(tst[i]); coord.pb(tst[i].se);
}
u=par[nu];
}
reverse(V.begin(),V.end());
sort(coord.begin(),coord.end()); coord.erase(unique(coord.begin(),coord.end()),coord.end());
//cerr<<coord.size()<<'\n';
init(int(coord.size()));
ll ans = 0; ll tot = 0;
for(ii x:V)
{
x.se = lower_bound(coord.begin(),coord.end(),x.se)-coord.begin();
ans += x.fi*(tot - query(x.se));
//cerr<<x.fi<<' '<<x.se<<'\n';
tot+=x.fi;
update(x.se, x.fi);
}
//cerr<<'\n';
return ans;
}
void addedge(int u, int v)
{
while(u!=-1)
{
int nu = nxt[u];
int siz = h[u] - h[nu] + 1;
while(chain[nu].size()>0)
{
int cnt = chain[nu][0].fi;
if(cnt<=siz)
{
chain[nu].pop_front();
siz-=cnt;
}
else
{
chain[nu].front().fi -= siz;
break;
}
}
chain[nu].push_front(mp(h[u]-h[nu]+1, v));
u=par[nu];
}
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
int n; cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
nxt[0] = 0; addtochain(0,a[0]);
vector<ii> edges;
par[0]=-1;
for(int i=0;i<n-1;i++)
{
int u,v; cin>>u>>v; u--; v--;
adj[u].pb(v); edges.pb(mp(u,v));
}
dfs_sz(); dfs_hld();
for(int i=0;i<n-1;i++)
{
cout<<calc_path(edges[i].fi)<<'\n';
addedge(edges[i].se, a[edges[i].se]);
//calc_path(edges[i].fi, edges[i].se);
}
}
