#include <bits/stdc++.h>
using namespace std;
const int N=1e5+3, MAXN=(1<<20);
int depth[N], pre[N], tree_size[N], anc[N][19];
int maxx[2*MAXN];
vector<int>V[N];
int a[N], b[N], c[N], num[N];
int licz=1;
void dfs(int v, int p, int d)
{
depth[v]=d;
anc[v][0]=p;
pre[v]=licz++;
tree_size[v]=1;
for(auto x:V[v])
{
if(x==p)continue;
dfs(x, v, d+1);
tree_size[v]+=tree_size[x];
}
}
void update(int x, int val)
{
x+=MAXN;
maxx[x]=val;
x/=2;
while(x>0)
{
maxx[x]=max(maxx[2*x], maxx[2*x+1]);
x/=2;
}
}
int query(int a, int b)
{
a+=MAXN-1, b+=MAXN+1;
int res=0;
while(a/2 != b/2)
{
if(a%2==0)res=max(res, maxx[a+1]);
if(b%2==1)res=max(res, maxx[b-1]);
a/=2, b/=2;
}
return res;
}
pair<vector<pair<int,int>>,long long> calc_ans(vector<pair<int,int>>vec)
{
if(vec.size()<=1) return {vec, 0};
vector<pair<int,int>>vec1, vec2;
for(int i=0; i<vec.size()/2; i++)vec1.push_back(vec[i]);
for(int i=vec.size()/2; i<vec.size(); i++)vec2.push_back(vec[i]);
auto X1=calc_ans(vec1), X2=calc_ans(vec2);
vec1=X1.first, vec2=X2.first;
long long res=X1.second+X2.second;
long long ind=0, ile=0;
for(int i=0; i<vec1.size(); i++)
{
while(ind<vec2.size()&&vec2[ind].first<vec1[i].first)
{
ile+=vec2[ind].second;
ind++;
}
res+=ile*vec1[i].second;
}
vec.clear();
int i=0, j=0;
while(i<vec1.size()||j<vec2.size())
{
if(i>=vec1.size())vec.push_back(vec2[j++]);
else if(j>=vec2.size())vec.push_back(vec1[i++]);
else if (vec1[i]<vec2[j])vec.push_back(vec1[i++]);
else vec.push_back(vec2[j++]);
}
return {vec, res};
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin>>n;
for(int i=1; i<=n; i++)cin>>c[i];
for(int i=1; i<n; i++)
{
cin>>a[i]>>b[i];
V[a[i]].push_back(b[i]);
V[b[i]].push_back(a[i]);
}
dfs(1,1,1);
for(int pot=1; pot<=17; pot++)
{
for(int i=1; i<=n; i++)
{
anc[i][pot]=anc[anc[i][pot-1]][pot-1];
}
}
num[0]=c[1];
for(int i=1; i<n; i++)
{
num[i]=c[b[i]];
vector<pair<int,int>>vec;
int wcz=a[i];
while(true)
{
int x=wcz, t=query(pre[x], pre[x]+tree_size[x]-1);
for(int pot=17; pot>=0; pot--)
{
int u=anc[x][pot];
if(t==query(pre[u], pre[u]+tree_size[u]-1))
{
x=u;;
}
}
vec.push_back({num[t], depth[wcz]-depth[x]+1});
if(x==1)break;
wcz=anc[x][0];
}
reverse(vec.begin(), vec.end());
// for(auto x:vec)cout<<x.first<<" "<<x.second<<"\n";
cout<<calc_ans(vec).second<<"\n";
update(pre[b[i]], i);
}
return 0;
}
