#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
#define mid ((left+right)>>1)
struct Fen{
int n;
int all=0;
vector<int>tree;
void init(int N){
n=N;
all=0;
tree.clear();
tree.resize(n+1,0);
}
void update(int tar,int x){
all+=x;
while(tar<=n){
tree[tar]+=x;
tar+=(tar&-tar);
}
}
int query(int tar){
int res=0;
while(tar>0){
res+=tree[tar];
tar-=(tar&-tar);
}
return res;
}
};
int n;
int arr[100023];
vector<int>child[100023];
int upd[100023];
int par[100023],sub[100023],dep[100023];
int bes[100023],bas[100023];
deque<pair<int,int>>v[100023];
Fen fen;
void dfs1(int pos){
sub[pos]=1;
for(int x:child[pos]){
dep[x]=dep[pos]+1;
dfs1(x);
sub[pos]+=sub[x];
if(sub[x]>sub[bes[pos]])bes[pos]=x;
}
}
void dfs2(int pos){
for(int x:child[pos]){
if(x==bes[pos])bas[x]=bas[pos];
else bas[x]=x;
dfs2(x);
}
}
signed main(){
ios_base::sync_with_stdio(23^23);cin.tie(0);
cin>>n;
fen.init(n);
for(int i=1;i<=n;i++){
cin>>arr[i];
}
for(int i=1;i<n;i++){
int x,y;cin>>x>>y;
upd[i]=y;
par[y]=x;
child[x].pb(y);
}
dep[1]=1;
dfs1(1);
bas[1]=1;
dfs2(1);
v[1].pb({arr[1],1});
for(int i=1;i<n;i++){
int pos=par[upd[i]];
vector<pair<int,int>>dizi;
while(pos){
int c=dep[bas[pos]]-1;
vector<pair<int,int>>sta;
while(c!=dep[pos]){
if(c+v[bas[pos]].back().sc>dep[pos]){
sta.pb({v[bas[pos]].back().fr,dep[pos]-c});
v[bas[pos]].back().sc-=dep[pos]-c;
c=dep[pos];
}
else{
sta.pb(v[bas[pos]].back());
c+=v[bas[pos]].back().sc;
v[bas[pos]].pop_back();
}
}
while(sta.size()){
dizi.pb(sta.back());
sta.pop_back();
}
v[bas[pos]].pb({arr[upd[i]],dep[pos]-dep[bas[pos]]+1});
pos=par[bas[pos]];
}
v[bas[upd[i]]].push_front({arr[upd[i]],1});
ll ans=0;
//cerr<<upd[i]<<": ";
for(auto x:dizi){
//cerr<<x.fr<<"-"<<x.sc<<" ";
ans+=ll(fen.query(x.fr-1))*ll(x.sc);
fen.update(x.fr,x.sc);
}
//cerr<<endl;
cout<<ans<<endl;
for(auto x:dizi){
fen.update(x.fr,-x.sc);
}
}
}
