#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int fen[MAXN],seg[MAXN*4],val[MAXN],A[MAXN],dis[MAXN],sub[MAXN],root[MAXN],pos[MAXN],rt[MAXN],tdfs=0;
set<int> st;
vector<int> ds[MAXN];
pair<int,int> Q[MAXN];
vector< pair<int,int> > req;
void updf(int i,int n,int val) { for(;i<=n;i+=i&-i) fen[i]+=val; }
int getf(int i) { int ans=0;for(;i;i-=i&-i) ans+=fen[i];return ans; }
void down(int pos)
{
if(seg[pos]!=-1) seg[pos*2]=seg[pos*2+1]=seg[pos],seg[pos]=-1;
}
void update(int l,int r,int u,int v,int val,int pos)
{
if(v<l||r<u) return ;
if(u<=l&&r<=v)
{
seg[pos]=val;
return ;
}
int mid=(l+r)/2;
down(pos);
update(l,mid,u,v,val,pos*2);
update(mid+1,r,u,v,val,pos*2+1);
}
int get(int l,int r,int i,int pos)
{
if(l==r) return seg[pos];
int mid=(l+r)/2;
down(pos);
if(i<=mid) return get(l,mid,i,pos*2);
return get(mid+1,r,i,pos*2+1);
}
void dfs(int i,int pre)
{
sub[i]=1;
for(auto v:ds[i]) if(v!=pre)
{
dis[v]=dis[i]+1;
dfs(v,i);
sub[i]+=sub[v];
}
}
void hld(int i,int pre)
{
pos[i]=++tdfs,rt[i]=pre;
if(i==pre) root[i]=i;
int mx=-1,pos=0;
for(auto v:ds[i]) if(v!=pre&&mx<sub[v]) mx=sub[v],pos=v;
if(mx!=-1)
{
root[pos]=root[i];
hld(pos,i);
}
for(auto v:ds[i]) if(v!=pre&&v!=pos)
{
root[v]=v;
hld(v,i);
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>A[i];
val[i]=A[i];
}
sort(val+1,val+n+1);
for(int i=1;i<=n*4;i++) seg[i]=-1;
for(int i=1;i<=n;i++) A[i]=lower_bound(val+1,val+n+1,A[i])-val;
for(int i=1;i<n;i++)
{
cin>>Q[i].first>>Q[i].second;
ds[Q[i].first].push_back(Q[i].second);
ds[Q[i].second].push_back(Q[i].first);
}
dfs(1,1);
hld(1,1);
for(int i=1;i<=n+1;i++)
{
st.insert(i);
update(1,n,pos[i],pos[i],A[i],1);
}
for(int i=1;i<n;i++)
{
int p=Q[i].first,w=get(1,n,pos[Q[i].second],1);
long long ans=0;
while(true)
{
int r=pos[p],l=pos[root[p]];
stack< pair<int,int> > vv;
while(l<=r)
{
auto res=st.upper_bound(l);
int v=get(1,n,l,1),nex=min(r+1,*res)-1;
vv.push({v,nex-l+1}),st.erase(l=nex+1);
}
while(!vv.empty())
{
int a=vv.top().first,b=vv.top().second;
req.push_back({a,b}),ans+=1LL*getf(a-1)*b,vv.pop();
updf(a,n,b);
}
update(1,n,pos[root[p]],r,w,1);
st.insert(l),st.insert(r+1);
if(root[p]==1) break;
p=rt[root[p]];
}
for(auto v:req) updf(v.first,n,-v.second);
req.clear();
cout<<ans<<"\n";
}
}
