#include <bits/stdc++.h>
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define pb push_back
#define X first
#define Y second
#define debug(x) cerr << #x << " : " << x << endl;
#define all(x) x.begin() , x.end()
using namespace std;
typedef pair<int,int> pll;
typedef long long ll;
constexpr int N = 1e5+10,lg = 18;
int tin[N],sz[N],seg[N*4],T,n;
int h[N],par[N][lg],c[N],fen[N];
vector<int> adj[N],ti,ci;
vector<pll> e;
void dfs(int v){
ti.pb(v);
tin[v] = T++;
sz[v] = 1;
for (int u : adj[v]){
h[u] = h[v]+1;
par[u][0] = v;
dfs(u);
sz[v] += sz[u];
}
}
void upd(int l,int r,int p,int x,int v = 1){
if (r-l == 1){
seg[v] = x;
return;
}
int m = (l+r) >> 1,u = (v << 1);
if (p < m) upd(l,m,p,x,u);
else upd(m,r,p,x,u|1);
seg[v] = max(seg[u],seg[u|1]);
}
int que(int l,int r,int s,int e,int v = 1){
if (l >= e || s >= r) return 0;
if (s <= l && r <= e) return seg[v];
int m = (l+r) >> 1,u = (v << 1);
return max(que(l,m,s,e,u),que(m,r,s,e,u|1));
}
void upd(int r,int x){
for (; r < n; r |= (r+1))
fen[r] += x;
}
int que(int l){
int ans = 0;
for (; l >= 0; l = (l&(l+1))-1)
ans += fen[l];
return ans;
}
int main(){
ios_base :: sync_with_stdio(0); cin.tie(0);
cin >> n;
rep(i,1,n+1){
cin >> c[i];
ci.pb(c[i]);
}
sort(all(ci));
rep(i,1,n+1){
c[i] = lower_bound(all(ci),c[i])-ci.begin();
}
e.pb({1,1});
rep(i,1,n){
int u,v;
cin >> u >> v;
e.pb({u,v});
adj[u].pb(v);
}
dfs(1);
rep(j,1,lg)
rep(i,2,n+1)
par[i][j] = par[par[i][j-1]][j-1];
rep(j,1,n){
int u = e[j].X,v = e[j].Y;
vector<pll> ve;
int cur = u;
while (cur){
int beg = cur,mx = que(0,n,tin[cur],tin[cur]+sz[cur]);
repr(i,lg-1,0){
if (!par[cur][i]) continue;
int w = par[cur][i];
if (que(0,n,tin[w],tin[w]+sz[w]) == mx) cur = w;
}
ve.pb({-h[cur]+h[beg]+1,c[e[mx].Y]});
cur = par[cur][0];
}
ll ans = 0;
for (auto a : ve){
ans += 1ll*a.X*que(a.Y-1);
upd(a.Y,a.X);
}
for (auto a : ve) upd(a.Y,-a.X);
upd(0,n,tin[v],j);
cout << ans << endl;
}
}
