# include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 2;
int n, c[N], a[N], b[N], h[N], fen[N], u[N];
int p[18][N], tin[N], tout[N], timer;
int t[N * 4];
vector <int> vec, g[N], vcc;
void dfs(int v, int pr = 0){
tin[v] = ++ timer;
p[0][v] = pr;
for(int i = 1; i <= 17; i ++)
p[i][v] = p[i - 1][p[i - 1][v]];
for(int to : g[v]){
if(to == pr) continue;
h[to] = h[v] + 1;
dfs(to, v);
}
tout[v] = timer;
}
inline bool upper(int a, int b){
return tin[a] <= tin[b] && tout[a] >= tout[b];
}
inline int lca(int a, int b){
if(upper(a, b)) return a;
if(upper(b, a)) return b;
for(int i = 17; i >= 0; i --)
if(p[i][a] && !upper(p[i][a], b))
a = p[i][a];
return p[0][a];
}
inline void update(int pos, int val, int v = 1, int tl = 1, int tr = n){
if(tl == tr)
t[v] = val;
else {
int tm = (tl + tr) >> 1;
if(pos <= tm)
update(pos, val, v << 1, tl, tm);
else
update(pos, val, (v << 1) | 1, tm + 1, tr);
t[v] = max(t[v << 1], t[(v << 1) | 1]);
}
}
inline int get(int l, int r, int v = 1, int tl = 1, int tr = n){
if(l > tr || tl > r) return 0;
if(l <= tl && tr <= r) return t[v];
int tm = (tl + tr) >> 1;
return max(get(l, r, v << 1, tl, tm),
get(l, r, (v << 1) | 1, tm + 1, tr));
}
inline void Update(int r, int val){
for(; r > 0; r = (r & (r + 1)) - 1){
fen[r] += val;
if(!u[r]){
u[r] = 1;
vcc.emplace_back(r);
}
}
}
inline int Get(int pos){
int res = 0;
for(; pos <= n; pos |= pos + 1)
res += fen[pos];
return res;
}
int main(){
ios_base::sync_with_stdio(0);
scanf("%d", &n);
for(int i = 1; i <= n; i ++){
scanf("%d", &c[i]);
vec.emplace_back(c[i]);
}
sort(vec.begin(), vec.end());
vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
for(int i = 1; i <= n; i ++)
c[i] = lower_bound(vec.begin(), vec.end(), c[i]) - vec.begin() + 1;
for(int i = 1; i < n; i ++){
scanf("%d %d", &a[i], &b[i]);
g[a[i]].emplace_back(b[i]);
g[b[i]].emplace_back(a[i]);
}
h[1] = 1;
dfs(1);
int siz = 0;
for(int i = 1; i < n; i ++){
int v = 1, prelca = 0;
long long ans = 0;
vcc.clear();
while(1){
siz ++;
int mx = b[get(tin[v], tout[v])];
int LCA = lca(mx, a[i]);
int f = h[LCA] - h[prelca], s = c[mx];
ans += Get(s + 1) * 1ll * f;
Update(s, f);
prelca = LCA;
if(v == a[i]) break;
int vv = a[i];
for(int i = 17; i >= 0; i --){
if(p[i][vv] && !upper(p[i][vv], LCA))
vv = p[i][vv];
}
v = vv;
}
if(siz >= n * 11) assert(0);
for(int j = 0; j < vcc.size(); j ++)
fen[vcc[j]] = 0, u[vcc[j]] = 0;
printf("%lld\n", ans);
update(tin[b[i]], i);
}
}
