#include<bits/stdc++.h>
using namespace std;
const int nmax=1e5+42;
int n,inp[nmax],help[nmax];
void compress()
{
for(int i=1;i<=n;i++)help[i]=inp[i];
sort(help+1,help+n+1);
for(int i=1;i<=n;i++)
{
inp[i]=lower_bound(help+1,help+n+1,inp[i])-help;
}
}
pair<int,int> edges[nmax];
vector<int> adj[nmax];
int parent[nmax];
int heaviest[nmax];
int SZ[nmax];
void dfs(int node,int par)
{
SZ[node]=1;
parent[node]=par;
for(auto k:adj[node])
if(k!=par)
{
dfs(k,node);
SZ[node]+=SZ[k];
if(SZ[k]>SZ[heaviest[node]])heaviest[node]=k;
}
}
struct info
{
int mini,maxi,lazy;
};
vector< int > path[nmax];
vector< info > tree[nmax];
void push(int id,int node)
{
if(tree[id][node].lazy!=-1)
{
tree[id][node*2].lazy=tree[id][node].lazy;
tree[id][node*2+1].lazy=tree[id][node].lazy;
}
tree[id][node].lazy=-1;
}
info actual(info ret)
{
if(ret.lazy!=-1)
{
ret.mini=ret.lazy;
ret.maxi=ret.lazy;
}
ret.lazy=-1;
return ret;
}
info my_merge(info l,info r)
{
l=actual(l);
r=actual(r);
info ret;
ret.lazy=-1;
ret.mini=min(l.mini,r.mini);
ret.maxi=max(l.maxi,r.maxi);
return ret;
}
void update(int id,int node,int l,int r,int lq,int rq,int val)
{
//cout<<"update "<<id<<" "<<node<<" "<<l<<" "<<r<<" "<<lq<<" "<<rq<<" "<<val<<endl;
if(l==lq&&r==rq)
{
tree[id][node].lazy=val;
return;
}
push(id,node);
int av=(l+r)/2;
if(lq<=av)update(id,node*2,l,av,lq,min(av,rq),val);
if(av<rq)update(id,node*2+1,av+1,r,max(av+1,lq),rq,val);
tree[id][node]=my_merge(tree[id][node*2],tree[id][node*2+1]);
}
int query(int id,int node,int l,int r,int pos)
{
if(l==r)return actual(tree[id][node]).mini;
push(id,node);
int av=(l+r)/2,mem;
if(pos<=av)mem=query(id,node*2,l,av,pos);
else mem=query(id,node*2+1,av+1,r,pos);
tree[id][node]=my_merge(tree[id][node*2],tree[id][node*2+1]);
return mem;
}
int query_range(int id,int node,int l,int r,int lq,int rq,int val)
{
//cout<<"query_range "<<id<<" "<<node<<" "<<l<<" "<<r<<" "<<lq<<" "<<rq<<" "<<val<<" "<<tree[id][node].lazy<<" "<<tree[id][node].mini<<" "<<tree[id][node].maxi<<endl;
if(tree[id][node].lazy!=-1)
{
//cout<<"go go "<<lq<<" "<<rq<<" "<<tree[id][node].lazy<<endl;
if(tree[id][node].lazy==val)return lq;
return rq+1;
}
if(tree[id][node].maxi<val||tree[id][node].mini>val)return rq+1;
push(id,node);
int av=(l+r)/2;
if(av<rq)
{
int mem=query_range(id,node*2+1,av+1,r,max(lq,av+1),rq,val);
if(mem!=max(lq,av+1))
{
tree[id][node]=my_merge(tree[id][node*2],tree[id][node*2+1]);
return mem;
}
}
if(lq<=av)
{
int mem=query_range(id,node*2,l,av,lq,min(av,rq),val);
if(mem!=lq)
{
tree[id][node]=my_merge(tree[id][node*2],tree[id][node*2+1]);
return mem;
}
}
tree[id][node]=my_merge(tree[id][node*2],tree[id][node*2+1]);
return lq;
}
int on_which[nmax];
int id[nmax];
void create_paths(int node,int par,int root)
{
on_which[node]=root;
id[node]=path[root].size();
path[root].push_back(node);
//cout<<node<<" -> "<<on_which[node]<<" "<<id[node]<<endl;
for(auto k:adj[node])
if(k!=par)
{
if(k==heaviest[node])create_paths(k,node,root);
else create_paths(k,node,k);
}
}
int fenwick[nmax];
int ask(int pos)
{
int ret=0;
while(pos)
{
ret+=fenwick[pos];
pos=pos-(pos&(-pos));
}
return ret;
}
void upd(int pos,int val)
{
while(pos<=n)
{
fenwick[pos]+=val;
pos=pos+(pos&(-pos));
}
}
long long eval(vector< pair<int/*value*/,int/*how much*/> > given)
{
long long outp=0;
for(auto k:given)
{
outp=outp+1LL*k.second*ask(k.first-1);
upd(k.first,k.second);
}
for(auto k:given)
{
upd(k.first,-k.second);
}
return outp;
}
int main()
{
scanf("%i",&n);
for(int i=1;i<=n;i++)scanf("%i",&inp[i]);
compress();
for(int i=1;i<n;i++)
{
scanf("%i%i",&edges[i].first,&edges[i].second);
adj[edges[i].first].push_back(edges[i].second);
adj[edges[i].second].push_back(edges[i].first);
}
dfs(1,0);
create_paths(1,0,1);
for(int i=1;i<=n;i++)
{
while(tree[i].size()<4*path[i].size())
{
info cur;
cur.lazy=-1;
cur.maxi=-1;
cur.mini=1e9;
tree[i].push_back(cur);
}
}
for(int i=1;i<=n;i++)
{
//cout<<"i= "<<i<<endl;
update(on_which[i],1,0,path[on_which[i]].size()-1,id[i],id[i],inp[i]);
}
for(int i=1;i<n;i++)
{
int where=edges[i].first;
int new_val=inp[edges[i].second];
vector< pair<int/*value*/,int/*how much*/> > given={};
while(where)
{
//cout<<"where= "<<i<<" "<<where<<endl;
int cur_value=query(on_which[where],1,0,path[on_which[where]].size()-1,id[where]);
int le=query_range(on_which[where],1,0,path[on_which[where]].size()-1,0,id[where],cur_value);
//cout<<"range: "<<le<<" "<<id[where]<<" "<<cur_value<<endl;
given.push_back({cur_value,id[where]-le+1});
update(on_which[where],1,0,path[on_which[where]].size()-1,le,id[where],inp[edges[i].second]);
where=path[on_which[where]][le];
where=parent[where];
//system("pause");
}
printf("%lld\n",eval(given));
}
return 0;
}
