#include <cstdio>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
const int NMAX = 1e5;
int n;
int ferikire[NMAX + 5];
pair<int,int> edges[NMAX + 5];
vector<int> graph[NMAX + 5];
int fst[NMAX + 5];
int snd[NMAX + 5];
int euler_len;
int lant_father[NMAX + 5];
int lvl[NMAX + 5];
int when[NMAX + 5];
void predfs(int nod,int tata){
lvl[nod] = 1 + lvl[tata];
fst[nod] = ++euler_len;
for(auto it:graph[nod]){
if(it == tata){
continue;
}
predfs(it,nod);
}
snd[nod] = euler_len;
}
pair<int,int> aint[NMAX + 5];
void update(int nod,int st,int dr,const int &pos,const pair<int,int> &val){
if(dr < pos || st > pos){
return;
}
if(st == dr){
aint[nod] = val;
return ;
}
int mid = (st + dr) / 2;
update(nod * 2,st,mid,pos,val);
update(nod * 2 + 1,mid + 1,dr,pos,val);
if(when[aint[2 * nod].second] > when[aint[2 * nod + 1].second]){
aint[nod] = aint[2 * nod];
}
else{
aint[nod] = aint[2 * nod + 1];
}
}
pair<int,int> query(int nod,int st,int dr,int l,int r){
if(l > dr || r < st){
return {0,-1};
}
if(l <= st && dr <= r){
return aint[nod];
}
int mid = (st + dr) / 2;
pair<int,int> a = query(nod * 2,st,mid,l,r);
pair<int,int> b = query(nod * 2 + 1,mid + 1,dr,l,r);
if(when[a.second] > when[b.second]){
return a;
}
else{
return b;
}
}
int aib[4 * NMAX + 5];
map<int,int> to_norm;
void aib_update(int pos,int val){
for(;pos <= NMAX;pos += (-pos) & pos){
aib[pos] += val;
}
}
int aib_query(int pos){
int ans = 0;
for(;pos;pos -= (-pos) & pos){
ans += aib[pos];
}
return ans;
}
int main(){
scanf("%d",&n);
for(int i = 1;i <= n;i++){
scanf("%d",&ferikire[i]);
to_norm[ferikire[i]] = 1;
}
int last = 0;
for(auto &it:to_norm){
it.second = ++last;
}
when[1] = 1;
for(int i = 1;i < n;i++){
int x,y;
scanf("%d %d",&x,&y);
graph[x].push_back(y);
graph[y].push_back(x);
edges[i] = {x,y};
when[y] = i + 1;
}
predfs(1,0);
update(1,1,n,fst[1],{ferikire[1],1});
lant_father[1] = 0;
for(int i = 1;i < n;i++){
int nod = edges[i].first;
long long ans = 0;
vector<pair<int,int> > to_clear;
while(nod != 0){
pair<int,int> _lant = query(1,1,n,fst[nod],snd[nod]);
ans += 1LL * (lvl[nod] - lvl[lant_father[_lant.second]]) * aib_query(to_norm[_lant.first] - 1);
aib_update(to_norm[_lant.first],lvl[nod] - lvl[lant_father[_lant.second]]);
to_clear.push_back({to_norm[_lant.first],lvl[lant_father[_lant.second]] - lvl[nod]});
int lst_nod = nod;
nod = lant_father[_lant.second];
lant_father[_lant.second] = lst_nod;
}
update(1,1,n,fst[edges[i].second],{ferikire[edges[i].second],edges[i].second});
lant_father[edges[i].second] = 0;
for(auto it:to_clear){
aib_update(it.first,it.second);
}
printf("%lld\n",ans);
}
return 0;
}
