#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
const int maxn=1e5+9;
int c[maxn];
vector<int>a[maxn];
int bit[maxn];
int n;
void add(int pos,int val){
for(;pos<=n;pos+=(pos-(pos&(pos-1))))bit[pos]+=val;
}
int get(int pos){
int sum=0;
for(;pos>=1;pos-=(pos-(pos&(pos-1))))sum+=bit[pos];
return sum;
}
pii b[maxn];
int head[maxn];
int sub[maxn];
int gr[maxn];
int p[maxn];
void dfs(int u,int par){
sub[u]=1;
p[u]=par;
for (auto &v:a[u]){
if (v==par)continue;
dfs(v,u);
sub[u]+=sub[v];
if (a[u][0]==par||sub[a[u][0]]<sub[v]){
swap(v,a[u][0]);
}
}
}
int tme=0,cnt=1;
int pos[maxn];
void hld(int u,int par,int h){
head[u]=h;
gr[u]=cnt;
pos[u]=++tme;
if (a[u][0]==par)return;
hld(a[u][0],u,h);
for (auto v:a[u]){
if (v==a[u][0]||v==par)continue;
cnt++;
hld(v,u,v);
}
}
struct line{
int l,r,val;
bool operator < (const line &p1)const {
return l<p1.l;
}
};
multiset<line>nw[maxn];
multiset<line>::iterator it;
long long addpath(int u,int val){
vector<pii>needtoerase;
int began=u;
long long ans=0;
while (u!=0){
line tmp;
tmp.l=pos[head[u]],tmp.r=pos[u],tmp.val=val;
if (!nw[gr[u]].empty()){
vector<pii>xoa;
while (!nw[gr[u]].empty()){
it=nw[gr[u]].begin();
auto t=(*it);
if (t.l>tmp.r)break;
if (t.r<=tmp.r){
xoa.pb({t.r-t.l+1,t.val});
nw[gr[u]].erase(it);
continue;
}
//tmp.l<=t.l<=tmp.r<=t.r
auto copyt=t;
copyt.l=tmp.r+1;
nw[gr[u]].erase(it);
nw[gr[u]].insert(copyt);
t.r=tmp.r;
xoa.pb({t.r-t.l+1,t.val});
}
reverse(all(xoa));
for (auto v:xoa){
needtoerase.pb(v);
long long bonus=1ll*v.fi*get(v.se-1);
add(v.se,v.fi);
ans+=bonus;
}
}
nw[gr[u]].insert(tmp);
u=p[head[u]];
}
for (auto v:needtoerase){
add(v.se,-v.fi);
//cout<<began<<" "<<v.fi<<" "<<v.se<<'\n';
}
return ans;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen("temp.INP","r",stdin);
//freopen(".OUT","w",stdout);
cin>>n;
vector<int>nen;
nen.pb(0);
map<int,int>nenso;
for1(i,1,n){
cin>>c[i];
nen.pb(c[i]);
}
sort(all(nen));
for1(i,1,sz(nen)-1){
if (nen[i]==nen[i-1])continue;
nenso[nen[i]]=nenso[nen[i-1]]+1;
}
for1(i,1,n){
c[i]=nenso[c[i]];
}
for1(i,1,n-1){
cin>>b[i].fi>>b[i].se;
a[b[i].fi].pb(b[i].se);
a[b[i].se].pb(b[i].fi);
}
dfs(1,0);
hld(1,0,1);
addpath(1,c[1]);
for1(i,1,n-1){
cout<<addpath(b[i].se,c[b[i].se])<<'\n';
}
}
