#include<bits/stdc++.h>
#define ll long long
#define int long long
const int nmax = 1e5 + 5, N = 1e6;
const ll oo = 1e9 + 1, base = 311;
const int lg = 19, M = 10;
const ll mod = 1e9 + 2277, mod2 = 1e9 + 5277;
#define pii pair<int, int>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;
int n, c[nmax];
pii a[nmax];
int sz[nmax], par[nmax];
vector<int> adj[nmax];
void dfs(int u, int p){
sz[u] = 1;
for(auto v : adj[u]){
if(v == p) continue;
par[v] = u;
dfs(v, u);
sz[u] += sz[v];
}
}
int head[nmax], ind[nmax], pos[nmax], Time = 0, nchain = 1;
int rev[nmax];
void dfs_2(int u, int p){
if(!head[nchain]) head[nchain] = u;
pos[u] = ++Time;
ind[u] = nchain;
rev[Time] = u;
int idx =-1;
for(auto v : adj[u]){
if(v == p) continue;
if(idx == -1 || sz[idx] < sz[v]){
idx = v;
}
}
if(idx != -1) dfs_2(idx, u);
for(auto v : adj[u]){
if(v == p) continue;
if(idx == v) continue;
++nchain;
dfs_2(v, u);
}
}
vector<pii> one;
struct Seg{
int ma[1 << 18], mi[1 << 18], lz[1 << 18];
void combine(int id){
ma[id] = max(ma[id << 1], ma[id << 1 | 1]);
mi[id] = min(mi[id << 1], mi[id << 1 | 1]);
}
void build(int id, int l, int r){
lz[id] = -1;
if(l == r){
ma[id] = mi[id] = c[rev[l]];
return;
}
int mid = r+ l >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
combine(id);
}
void fix(int id, int val){
if(val == -1) return;
ma[id] = val;
mi[id] = val;
lz[id] = val;
}
void down(int id){
fix(id << 1, lz[id]);
fix(id << 1| 1, lz[id]);
lz[id] = -1;
}
void update(int id, int l, int r, int u, int v, int val){
if(l > v || r < u) return;
if(l >= u && r <= v) return fix(id, val);
down(id);
int mid = r + l >> 1;
update(id << 1, l, mid, u, v,val);
update(id << 1 | 1, mid + 1, r, u, v,val);
combine(id);
}
void get(int id, int l, int r, int u, int v){
if(l > v || r < u) return;
if(l >= u && r <= v && ma[id] == mi[id]){
one.push_back({r - l + 1, ma[id]});
return;
}
down(id);
int mid = r + l >> 1;
get(id << 1 | 1, mid + 1, r, u, v);
get(id << 1, l, mid, u, v);
}
int Find(int id, int l, int r, int u){
if(l == r) return ma[id];
down(id);
int mid = r + l >> 1;
if(mid < u) return Find(id << 1 | 1, mid + 1, r, u);
else return Find(id << 1,l,mid, u);
}
}tree;
struct FEN{
ll f[nmax];
vector<int> tmp;
void update(int x, int val){
for(; x <= n; x += x&-x) f[x] += val, tmp.push_back(x);
}
ll get(int x){
ll cur = 0;
for(; x; x -= x&-x) cur += f[x];
return cur;
}
void clear(){
for(auto p : tmp) f[p] = 0;
tmp.clear();
}
}F;
ll calc(int u, int x){
int A = u;
int uchain = ind[u];
one.clear();
while(1){
if(uchain == 1){
tree.get(1, 1, n, pos[1], pos[u]);
tree.update(1, 1, n, pos[1], pos[u], c[x]);
break;
}
tree.get(1, 1, n, pos[head[uchain]], pos[u]);
tree.update(1, 1, n, pos[head[uchain]], pos[u], c[x]);
u = par[head[uchain]];
uchain = ind[u];
}
ll ans = 0;
// cout << A << ' ' << x << "#"<< ' ' << c[x] << endl;
// for(int i = 1; i <= n; ++i) cout << tree.Find(1, 1, n, pos[i]) << ' ';
// cout << endl;
for(auto [x, y] : one){
ans += 1ll * F.get(y - 1) * x;
F.update(y, x);
// cout << x << ' ' << y << endl;
}
F.clear();
return ans;
}
main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("code.inp", "r", stdin);
// freopen("code.out", "w", stdout);
cin >> n;
vector<int> nen;
for(int i = 1; i <= n; ++i) cin >> c[i],nen.push_back(c[i]);
sort(nen.begin(), nen.end());
nen.erase(unique(nen.begin(), nen.end()), nen.end());
for(int i = 1; i <= n; ++i) c[i] = lower_bound(nen.begin(), nen.end(),c[i]) - nen.begin() + 1;
for(int i = 1; i < n; ++i){
int x, y;
cin >> a[i].fi >> a[i].se;
adj[a[i].fi].push_back(a[i].se);
}
dfs(1, -1);
dfs_2(1, -1);
// for(int i = 1; i <= n; ++i) cout << c[i] << ' ';
tree.build(1, 1, n);
// for(int i = 1; i <= n; ++i) cout << tree.Find(1, 1, n, pos[i]) << ' ';
// ll ans = 0;
for(int i = 1; i < n; ++i){
int x = a[i].fi, y = a[i].se;
// calc(x, y);
cout << calc(x, y) << endl;
}
}
/*
*/
