#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1000001;
const int SIZE = 1<<17;
#define ff first
#define ss second
int A[MAXN], B[MAXN], C[MAXN], dth[MAXN], prt[17][MAXN], dfn[MAXN], edfn[MAXN], dfnn;
vector<int> edge[100001];
void dfs(int x){
dfn[x] = ++dfnn;
for(auto &i: edge[x]){
prt[0][i] = x;
dth[i] = dth[x]+1;
dfs(i);
}
edfn[x] = dfnn;
}
struct ST{
int data[2*SIZE];
void update(int x, int v){
for(x+=SIZE; x; x>>=1)
data[x] = max(data[x], v);
}
int query(int s, int e){
int ret = 0;
for(s+=SIZE, e+=SIZE; s<=e; s>>=1, e>>=1){
if(s&1) ret = max(ret, data[s++]);
if(~e&1) ret = max(ret, data[e--]);
}
return ret;
}
int lb(int x, int v){
for(x+=SIZE; data[x]<=v; x=(x-1)/2);
for(; x<SIZE; x = x<<1|(data[x<<1|1]>v));
return x-SIZE;
}
int rb(int x, int v){
for(x+=SIZE; data[x]<=v; x=(x+1)/2);
for(; x<SIZE; x = (x<<1|1)-(data[x<<1]>v));
return x-SIZE;
}
} seg;
struct BIT{
int data[SIZE+1];
void update(int x, int v){
for(; x<=SIZE; x+=x&-x) data[x] += v;
}
int query(int x){
int ret=0;
for(; x; x-=x&-x) ret+= data[x];
return ret;
}
} bit;
vector<int> cc;
int main(){
int N;
scanf("%d",&N);
for(int i=1; i<=N; ++i) scanf("%d",C+i), cc.push_back(C[i]);
sort(cc.begin(), cc.end());
cc.erase(unique(cc.begin(), cc.end()), cc.end());
for(int i=1; i<=N; ++i) C[i] = lower_bound(cc.begin(), cc.end(), C[i])-cc.begin()+1;
for(int i=1; i<N; ++i){
scanf("%d%d",A+i,B+i);
edge[A[i]].push_back(B[i]);
}
B[0] = 1;
dth[1] = 1;
dfs(1);
for(int i=1; i<17; ++i)for(int j=1; j<=N; ++j) prt[i][j] = prt[i-1][prt[i-1][j]];
seg.update(0, 1e9); seg.update(N+1, 1e9);
for(int i=1; i<N; ++i){
int x = A[i];
long long ans = 0;
vector<pair<int, int> > vec;
while(x){
int t = seg.query(dfn[x], edfn[x]);
int l = seg.lb(dfn[x], t), r = seg.rb(edfn[x], t);
int y = x;
for(int j=16; j>=0; --j) if(l<dfn[prt[j][x]] && r>edfn[prt[j][x]]) x = prt[j][x];
x = prt[0][x];
vec.push_back({C[B[t]], dth[y]-dth[x]});
}
for(auto &i: vec){
ans += 1ll*bit.query(i.ff-1)*i.ss;
bit.update(i.ff, i.ss);
}
printf("%lld\n",ans);
for(auto &i: vec) bit.update(i.ff, -i.ss);
seg.update(dfn[B[i]], i);
}
return 0;
}
