#include <vector>
#include <iostream>
#include <random>
#include <cassert>
#include <tuple>
#include <algorithm>
using namespace std;
using nagai = long long;
#define sz(x) int((x).size())
const int LG=17;
const int N=1<<LG;
struct v{
int mn,mx,psh;
} t[2*N];
void push1(int u){
if(t[u].psh){
t[u*2].psh=t[u*2+1].psh=t[u].psh;
t[u*2].mn=t[u*2+1].mn=t[u*2].mx=t[u*2+1].mx=t[u].psh;
t[u].psh=0;
}
}
void push(int u){
for(int i=LG;i>0;--i)
push1(u>>i);
}
void upd(int u){
t[u].mn=min(t[u*2+1].mn,t[u*2].mn);
t[u].mx=max(t[u*2].mx,t[u*2+1].mx);
}
void st(int u,int l,int r,int ql,int qr,int v){
if(l>=qr||ql>=r)return;
if(ql<=l&&r<=qr){
t[u]={v,v,v};
return;
}
push1(u);
int m=(l+r)/2;
st(u*2,l,m,ql,qr,v);
st(u*2+1,m,r,ql,qr,v);
upd(u);
}
int getr(int u,int l,int r,int ql,int v=-1){
if(u==1){
push(ql+N);
v=t[ql+N].mn;
}
if(v<t[u].mn||v>t[u].mx)return l;
if(t[u].mn==t[u].mx)
return r;
push1(u);
int m=(l+r)/2;
if(m<=ql)return getr(u*2+1,m,r,ql,v);
int kek=getr(u*2,l,m,ql,v);
if(kek==m){
return getr(u*2+1,m,r,ql,v);
}
return kek;
}
int n;
int C[N];
vector<int>g[N];
vector<int>ch[N];
int sz[N];
void d1(int u,int p=-1){
sz[u]=1;
for(int v:g[u]){
if(v==p)continue;
d1(v,u);
sz[u]+=sz[v];
ch[u].push_back(v);
if(sz[v]>sz[ch[u][0]])
swap(ch[u].back(),ch[u].front());
}
}
int tin[N];
int tot=0;
int top[N];
int par[N];
void d2(int u){
tin[u]=tot++;
for(int v:ch[u]){
par[v]=u;
top[v]=v==ch[u][0]?top[u]:v;
d2(v);
}
}
void st(int u,int col){
while(true){
int tp=top[u];
st(1,0,N,tin[tp],tin[u]+1,col);
if(tp==0)return;
u=par[tp];
}
}
vector<pair<int,int>>glob;
void gt1(int l,int r){
while(true){
int kek=getr(1,0,N,l);
int v=t[N+l].mn;
if(kek>=r){
glob.emplace_back(r-l,v);
return;
}
glob.emplace_back(kek-l,v);
l=kek;
}
}
void gt(int u){
glob.clear();
vector<pair<int,int>>p;
while(true){
int tp=top[u];
p.emplace_back(tin[tp],tin[u]+1);
if(tp==0)break;
u=par[tp];
}
reverse(p.begin(),p.end());
for(auto q:p)gt1(q.first,q.second);
}
struct it{
int t[2*N];
int get(int l,int r){
l+=N;
r+=N;
int ans=0;
while(l<r){
if(l&1)ans+=t[l++];
if(r&1)ans+=t[--r];
l/=2,r/=2;
}
return ans;
}
void inc(int x,int y){
x+=N;
t[x]+=y;
while(x>1)t[x>>1]=t[x]+t[x^1],x>>=1;
}
} myit;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
n=100000;
cin>>n;
for(int i=0;i<n;++i){
C[i]=i;
cin>>C[i];
}
vector<pair<int,int>>p;
for(int i=0;i<n-1;++i){
int a=rand()%(i+1),b=i+1;
cin>>a>>b;
--a,--b;
p.emplace_back(a,b);
g[a].push_back(b);
g[b].push_back(a);
}
vector<int>cs(C,C+n);
sort(cs.begin(),cs.end());
for(int i=0;i<n;++i)
C[i]=lower_bound(cs.begin(),cs.end(),C[i])-cs.begin()+1;
d1(0);
d2(0);
st(0,C[0]);
int s=0;
for(auto q:p){
int a,b;
tie(a,b)=q;
gt(a);
auto&lol=glob;
s+=lol.size();
nagai ans=0;
for(int i=0;i<lol.size();++i){
ans+=(nagai)lol[i].first*myit.get(lol[i].second+1,N);
myit.inc(lol[i].second,lol[i].first);
}
for(int i=0;i<lol.size();++i)
myit.inc(lol[i].second,-lol[i].first);
cout<<ans<<'\n';
st(b,C[b]);
}
return 0;
}
