#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
int inf = 1e18;
const int mod = 1e9 + 7;
const int N = 2e5 + 5;
struct bitt {
vector<int> t;
int n;
bitt (int N) : n(N+1) {
t.resize(n+2);
};
void upd(int i, int va) { i ++ ;
for(; i < n; i += (i & -i)) t[i] += va;
};
int get(int i) { i ++ ;
int res = 0;
for(; i > 0; i -= (i & -i)) res += t[i];
return res;
};
int get(int l, int r) { r--;
return get(r ) - get( -- l );
};
}bt(N);
struct segt {
vector<int> t, b;
int n;
segt (int N) : n(N+3) {
t.resize(n);
b.resize(n*4);
};
void push(int i, int l, int r) {
if(b[i] == 0)return;
if(l == r) t[l] = b[i];
else{
b[i << 1] = b[i];
b[i << 1 | 1] = b[i];
};
b[i] = 0;
};
void upd(int tl, int tr, int va, int i, int l, int r) {
push(i, l, r);
if(l > tr || r < tl) return;
if(tl <= l && r <= tr) {
b[i] = va;
push(i, l, r);
return;
};
int m = (l + r) >> 1;
upd(tl, tr, va, i << 1, l, m);
upd(tl, tr, va, i << 1 | 1, m + 1, r);
};
void upd(int l, int r, int va) {
upd(l, r, va, 1, 1, n);
};
int get(int ps, int i, int l, int r) {
push(i,l,r);
if(l == r) return t[l];
int m = (l + r) >> 1;
if(ps <= m) return get(ps, i << 1, l, m);
else return get(ps, i << 1 | 1, m + 1, r);
};
int get(int ps) {
return get(ps, 1, 1, n);
};
}t(N);
vector<vector<int>> g(N);
int sz[N], pr[N], head[N], heavy[N], dep[N], id[N];
int tim = 1;
int ls[22][N];
void dfs(int ps, int par) {
sz[ps] = 1;
pr[ps] = par;
heavy[ps] = 0;
ls[0][ps] = par;
for(int i = 1; i < 22; i ++ )
ls[i][ps] = ls[i-1][ls[i-1][ps]];
for(int to : g[ps]) {
if(to == par)continue;
dep[to] = dep[ps] + 1;
dfs(to, ps);
sz[ps] += sz[to];
if(sz[heavy[ps]] < sz[to]) heavy[ps] = to;
}
}
void hld(int ps, int hd) {
head[ps] = hd;
id[ps] = tim ++ ;
if(heavy[ps])
hld(heavy[ps], hd);
for(int to : g[ps]){
if(to == pr[ps] || to == heavy[ps])continue;
hld(to, to);
}
};
int query(int ps) {
vector<array<int,2>> updates;
int ans = 0;
while(1) {
int to = ps, curv = t.get(id[ps]);
for(int i = 21; i >= 0; i -- ) {
int r = ls[i][to];
if(t.get(id[r]) != curv)continue;
to = r;
}
int cnt = dep[ps] - dep[to] + 1;
//cout << ps << ' ' << to << ' ' << curv << ' ' << cnt << '\n';
ans += bt.get(curv - 1) * cnt;
bt.upd(curv, cnt);
updates.push_back({curv, cnt});
if(to == 1)break;
ps = pr[to];
};
for(auto [a, b] : updates) bt.upd(a, -b);
return ans;
};
void upd (int ps, int va) {
while(1) {
t.upd(id[head[ps]], id[ps], va);
//cout << ps << ' ' << head[ps] << '\n';
if(head[ps] == 1)return;
ps = pr[head[ps]];
}
};
void solve(){
int n; cin >> n;
vector<int> a(n+1);
for(int i = 1; i <= n; i++ )cin >> a[i];
vector<int> b = a;
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());
for(int i = 1; i <= n; i ++ )a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
vector<array<int,2>> ed(n-1);
for(auto &[a, b] : ed) {
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
for(auto &i : ls) for(auto &j : i)j = 1;
dfs(1, 1);
hld(1, 1);
for(int i = 1; i <= n; i ++ ) t.upd(id[i], id[i], a[i]);
//for(int i = 1; i <= n; i ++ ) {
//cout << dep[i] << ' ' << sz[i] << ' ' << head[i] << '\n';
//}
for(auto [u, v] : ed) {
cout << query(u) << '\n';
//for(int i = 1; i <= n; i ++ ) cout << t.get(id[i]) << ' ';
//cout << '\n';
upd(u, a[v]);
};
};
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int tt = 1;
//cin >> tt;
while(tt -- ){
solve();
};
};
