#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=100010, L=18, S=(1<<17);
int n, a[N], b[N], c[N];
int par[L][N], siz[N], dep[N], t, in[N], top[N], gp[N];
vector<int> com;
vector<int> adj[N];
class LazyProp {
public:
void update(int l, int r, int v) {update(1, 1, S, l, r, v);}
int query(int k) {return query(1, 1, S, k);}
private:
int tree[2*S], lazy[2*S];
void propagate(int node, int s, int e) {
if (!lazy[node]) return;
if (s!=e) lazy[2*node]=lazy[2*node+1]=lazy[node];
else tree[node]=lazy[node];
lazy[node]=0;
}
void update(int node, int s, int e, int l, int r, int v) {
propagate(node, s, e);
if (s>r || l>e) return;
if (l<=s && e<=r) {
lazy[node]=v, propagate(node, s, e);
return;
}
int lch=2*node, rch=lch+1, m=(s+e)/2;
update(lch, s, m, l, r, v), update(rch, m+1, e, l, r, v);
}
int query(int node, int s, int e, int k) {
propagate(node, s, e);
if (s==e) return tree[node];
int lch=2*node, rch=lch+1, m=(s+e)/2;
if (k<=m) return query(lch, s, m, k);
return query(rch, m+1, e, k);
}
}T;
class Fenwick {
public:
void update(int k, int v) {
for (int i=k; i<=n; i+=i&-i) tree[i]+=v;
}
int query(int k) {
int ret=0;
for (int i=k; i>=1; i-=i&-i) ret+=tree[i];
return ret;
}
private:
int tree[N];
}T2;
void dfs(int curr) {
for (int i=1; i<L; i++) par[i][curr]=par[i-1][par[i-1][curr]];
siz[curr]=1;
for (int next:adj[curr]) {
par[0][next]=curr, dep[next]=dep[curr]+1, dfs(next), siz[curr]+=siz[next];
}
for (int &next:adj[curr]) if (siz[next]>siz[adj[curr][0]]) swap(next, adj[curr][0]);
}
void dfs2(int curr) {
in[curr]=++t;
for (int next:adj[curr]) {
if (next==adj[curr][0]) top[next]=top[curr];
else top[next]=next;
dfs2(next);
}
}
int lift(int x, int y) {
for (int i=L-1; i>=0; i--) if (par[i][x] && dep[par[i][x]]>dep[y]) x=par[i][x];
return x;
}
int query(int x) {
vector<array<int, 2>> vec;
while (x) {
int tmp=T.query(in[x]);
vec.push_back({c[tmp], dep[x]-dep[gp[tmp]]+1});
int ttmp=par[0][gp[tmp]];
gp[tmp]=lift(tmp, x);
x=ttmp;
}
int ret=0;
for (int i=0; i<vec.size(); i++) {
ret+=T2.query(vec[i][0]-1)*vec[i][1], T2.update(vec[i][0], vec[i][1]);
}
for (int i=0; i<vec.size(); i++) T2.update(vec[i][0], -vec[i][1]);
return ret;
}
void update(int x, int v) {
gp[v]=1;
while (x) T.update(in[top[x]], in[x], v), x=par[0][top[x]];
}
signed main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin>>n;
for (int i=1; i<=n; i++) cin>>c[i], com.push_back(c[i]);
sort(com.begin(), com.end()), com.erase(unique(com.begin(), com.end()), com.end());
for (int i=1; i<=n; i++) c[i]=lower_bound(com.begin(), com.end(), c[i])-com.begin()+1;
for (int i=1; i<n; i++) {
cin>>a[i]>>b[i];
adj[a[i]].push_back(b[i]);
}
dfs(1), dfs2(1);
for (int i=1; i<=n; i++) T.update(in[i], in[i], i), gp[i]=i;
for (int i=1; i<n; i++) {
cout<<query(a[i])<<"\n";
update(a[i], b[i]);
}
return 0;
}
