#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int range_rng(int l, int r)
{
return uniform_int_distribution<int>(l,r)(rng);
}
int c[100005];
int x[100005];
int y[100005];
int sz[100005];
int h[100005];
int heavychild[100005];
int pathend[100005];
int p[100005];
vector<int> nodes[100005];
deque<pair<int,int>> lant[100005];
void dfs(int node, int parent)
{
int mx;
sz[node]=1;
p[node]=parent;
mx=0;
for (auto x : nodes[node])
{
if (x!=parent)
{
h[x]=h[node]+1;
dfs(x,node);
sz[node]+=sz[x];
if (sz[x]>sz[mx])
mx=x;
}
}
heavychild[node]=mx;
}
void heavyfirst(int node, int parent, int capat)
{
//lant[capat].push_back(node);
pathend[node]=capat;
if (heavychild[node]==0)
return;
heavyfirst(heavychild[node],node,capat);
for (auto x : nodes[node])
{
if (x!=heavychild[node] && x!=parent)
{
heavyfirst(x,node,x);
}
}
}
class AIB
{
public:
int aib[100005];
int lim;
void clr()
{
int i;
for (i=1; i<=lim; i++)
{
aib[i]=0;
}
}
void update(int idx, int delta)
{
while(idx<=lim)
{
aib[idx]+=delta;
idx+=idx&(-idx);
}
}
int query(int idx)
{
int ans;
ans=0;
while (idx>0)
{
ans+=aib[idx];
idx-=idx&(-idx);
}
return ans;
}
} aib;
vector<pair<int,int>> pathvals;
vector<pair<int,int>> aux;
vector<int> idk;
map<int,int> normval;
int build_cost(int v)
{
int currnode,diff;
pathvals.clear();
currnode=v;
while (currnode!=0)
{
diff=h[currnode]-h[pathend[currnode]]+1;
aux.clear();
for (auto x : lant[pathend[currnode]])
{
if (diff>x.second)
{
aux.push_back(x);
diff-=x.second;
}
else
{
aux.push_back({x.first,diff});
reverse(aux.begin(),aux.end());
for (auto x : aux)
pathvals.push_back(x);
break;
}
}
currnode=p[pathend[currnode]];
}
idk.clear();
for (auto x : pathvals)
{
idk.push_back(x.first);
}
sort(idk.begin(),idk.end());
int currval,i;
currval=0;
normval.clear();
for (i=0; i<idk.size(); i++)
{
if (i==0 || idk[i]!=idk[i-1])
currval++;
normval[idk[i]]=currval;
}
aib.lim=currval;
aib.clr();
int ans;
ans=0;
for (auto x : pathvals)
{
ans+=x.second*(aib.query(normval[x.first]));
aib.update(normval[x.first]+1,x.second);
}
return ans;
}
void add_edge(int u, int v)
{
int currnode,diff,total;
currnode=u;
while (currnode!=0)
{
diff=h[currnode]-h[pathend[currnode]]+1;
total=diff;
while (diff>0)
{
pair<int,int> fr;
fr=lant[pathend[currnode]].front();
if (diff>fr.second)
{
diff-=fr.second;
lant[pathend[currnode]].pop_front();
}
else
{
if (fr.second!=diff)
lant[pathend[currnode]].front().second-=diff;
else
lant[pathend[currnode]].pop_front();
lant[pathend[currnode]].push_front({c[v],total});
diff=0;
}
}
currnode=p[pathend[currnode]];
}
if (!lant[pathend[v]].empty())
lant[pathend[v]].back().second++;
else
lant[pathend[v]].push_back({c[v],1});
}
signed main()
{
//ifstream fin("secvp.in");
//ofstream fout("secvp.out");
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,i,u,v;
cin >> n;
for (i=1; i<=n; i++)
{
cin >> c[i];
}
for (i=1; i<=n-1; i++)
{
cin >> u >> v;
x[i]=u;
y[i]=v;
nodes[u].push_back(v);
nodes[v].push_back(u);
}
h[1]=1;
dfs(1,0);
heavyfirst(1,0,1);
lant[1].push_back({c[1],1});
for (i=1; i<=n-1; i++)
{
cout << build_cost(x[i]) << "\n";
add_edge(x[i],y[i]);
}
return 0;
}
