#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long
const int N=100050;
vector<int> E[N];
int c[N];
struct BIT
{
int sum[N];
vector<int> use;
void init(){ for(int i=0;i<use.size();i++) sum[use[i]]=0;use.clear();}
BIT(){}
void Set(int i, int x){ for(;i<N;i+=i&-i){ if(!sum[i]) use.pb(i);sum[i]+=x;}}
int Get(int i){ int ret=0;for(;i;i-=i&-i) ret+=sum[i];return ret;}
} Tree;
int sz[N],head[N],dep[N],par[N];
vector<pair<int,int> > all[N];
void DFS(int u, int p)
{
dep[u]=dep[p]+1;
par[u]=p;
sz[u]=1;
for(int i=0;i<E[u].size();i++)
{
int v=E[u][i];
if(v!=p) DFS(v,u),sz[u]+=sz[v];
}
}
void HLD(int u, int p)
{
if(!p) head[u]=u;
int HC=0,i;
for(i=0;i<E[u].size();i++)
{
int v=E[u][i];
if(v!=p && sz[v]>sz[HC]) HC=v;
}
for(i=0;i<E[u].size();i++)
{
int v=E[u][i];
if(v!=p)
{
if(v==HC) head[v]=head[u];
else head[v]=v;
HLD(v,u);
}
}
}
ll Query(int u, int v)
{
ll ans=0;
int col=c[v];
vector<pair<int,int> > work;
while(u)
{
int len=dep[u]-dep[head[u]]+1;
int chain=head[u];
work.clear();
while(all[chain].size() && len>=all[chain].back().first)
{
work.pb(all[chain].back());
len-=all[chain].back().first;
all[chain].pop_back();
}
if(all[chain].size() && len>0)
{
work.pb(mp(len,all[chain].back().second));
all[chain][all[chain].size()-1].first-=len;
}
while(work.size())
{
ans+=(ll)work.back().first*Tree.Get(work.back().second-1);
Tree.Set(work.back().second,work.back().first);
//printf("del:%i %i\n",work.back().first,work.back().second);
work.pop_back();
}
u=par[head[u]];
}
while(v)
{
int push=dep[v]-dep[head[v]]+1;
all[head[v]].pb(mp(push,col));
//printf("add:%i %i\n",push,col);
//printf("%i %i %i %i\n",head[v],v,push,col);
v=par[head[v]];
}
Tree.init();
return ans;
}
vector<int> id;
int Find(int x){ return lower_bound(id.begin(),id.end(),x)-id.begin()+1;}
int a[N],b[N];
int main()
{
int n,i,u,v;
scanf("%i",&n);
for(i=1;i<=n;i++) scanf("%i",&c[i]),id.pb(c[i]);
sort(id.begin(),id.end());
id.erase(unique(id.begin(),id.end()),id.end());
for(i=1;i<=n;i++) c[i]=Find(c[i]);
for(i=1;i<n;i++) scanf("%i %i",&u,&v),E[u].pb(v),a[i]=u,b[i]=v;
DFS(1,0);
HLD(1,0);
all[1].pb(mp(1,c[1]));
for(i=1;i<n;i++) printf("%lld\n",Query(a[i],b[i]));
return 0;
}
