# pragma GCC optimize ("O3")
# pragma GCC optimize ("Ofast")
# pragma GCC optimize ("unroll-loops")
# pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#include <bits/stdc++.h>
using namespace std;
int n;
int arr[100000];
vector<int> adj[100000];
typedef pair<int,int> P;
P edge[100000];
int p[100000];
int ind[100000];
int siz[100000];
int f=0;
int depth[100000];
int par[100000][17];
void dfs(int v,int prev) {
ind[v]=f++;
siz[v]=1;
p[v]=prev;
for(int i=0;i<adj[v].size();i++) {
int nt=adj[v][i];
if (nt==prev) {
continue;
}
depth[nt]=depth[v]+1;
dfs(nt,v);
siz[v]+=siz[nt];
}
}
const int sz=131072;
P seg[sz*2];
P pmax(P a,P b) {
return a<b?b:a;
}
P sum(int l,int r,int node=1,int nodel=0,int noder=sz-1) {
if (r<nodel||l>noder) {
return P(0,0);
}
if (l<=nodel&&noder<=r) {
return seg[node];
}
int mid=(nodel+noder)/2;
return pmax(sum(l,r,node*2,nodel,mid),sum(l,r,node*2+1,mid+1,noder));
}
void update(int i,P val) {
i+=sz;
seg[i]=val;
while (i>1) {
i/=2;
seg[i]=pmax(seg[i*2],seg[i*2+1]);
}
}
struct SegmentTree {
vector<int> seg;
int sz=1;
void init(int x) {
seg.resize(x+1);
sz=x;
}
int sum(int i) {
int ret=0;
while (i>0) {
assert(i<seg.size());
ret+=seg[i];
i-=(i&-i);
}
return ret;
}
void update(int i,int val) {
while (i<=sz) {
assert(i<seg.size());
seg[i]+=val;
i+=(i&-i);
}
}
};
long long cntinv(vector<P> v) {
vector<int> press;
press.push_back(-1);
for(int i=0;i<v.size();i++) {
//printf("%d %d\n",v[i].first,v[i].second);
press.push_back(v[i].first);
}
sort(press.begin(),press.end());
press.erase(unique(press.begin(),press.end()),press.end());
SegmentTree st;
st.init(press.size());
long long ret=0;
for(int i=0;i<v.size();i++) {
v[i].first=lower_bound(press.begin(),press.end(),v[i].first)-press.begin();
assert(v[i].first!=0);
ret+=1LL*v[i].second*st.sum(v[i].first-1);
st.update(v[i].first,v[i].second);
}
return ret;
}
int main(void) {
scanf("%d",&n);
for(int i=0;i<n;i++) {
scanf("%d",&arr[i]);
}
vector<int> press;
for(int i=0;i<n;i++) {
press.push_back(arr[i]);
}
sort(press.begin(),press.end());
press.erase(unique(press.begin(),press.end()),press.end());
for(int i=0;i<n;i++) {
arr[i]=lower_bound(press.begin(),press.end(),arr[i])-press.begin();
}
for(int i=1;i<n;i++) {
int u,v;
scanf("%d %d",&u,&v);
u--;
v--;
edge[i]=P(u,v);
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(0,-1);
memset(par,-1,sizeof(par));
for(int i=0;i<n;i++) {
par[i][0]=p[i];
}
for(int j=1;j<17;j++) {
for(int i=0;i<n;i++) {
if (par[i][j-1]!=-1) {
par[i][j]=par[par[i][j-1]][j-1];
}
}
}
for(int i=1;i<n;i++) {
int now=edge[i].first;
vector<P> vec;
while (now!=-1) {
int rec=now;
int deep=sum(ind[now],ind[now]+siz[now]-1).second;
for(int j=16;j>=0;j--) {
int nt=par[rec][j];
if (nt==-1) {
continue;
}
if (sum(ind[nt],ind[nt]+siz[nt]-1).second==deep) {
rec=nt;
}
}
vec.push_back(P(arr[deep],depth[now]-depth[rec]+1));
now=p[rec];
}
update(ind[edge[i].second],P(i,edge[i].second));
printf("%lld\n",cntinv(vec));
}
}
