#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#define fs first
#define se second
using namespace std;
typedef long long llong;
typedef pair<int, int> pii;
int n;
int C[100001];
int A[100001];
int B[100001];
vector<int> child[100001];
int sz[100001];
int dep[100001];
int par[100001];
void dfs1(int x) {
sz[x] = 1;
for (int i : child[x]) {
dep[i] = dep[x] + 1;
dfs1(i);
sz[i] += sz[x];
}
sort(child[x].begin(), child[x].end(), [&](int a, int b) {
return sz[a] > sz[b];
});
}
int hidx[100001];
int st[100001];
int re[100001];
void dfs2(int x) {
static int ord = 0;
if (hidx[x] == 0) hidx[x] = x;
re[st[x] = ++ord] = x;
if (child[x].empty()) return;
hidx[child[x][0]] = hidx[x];
for (int i : child[x]) {
dfs2(i);
}
}
set<pii> sp;
vector<pii> gs;
void hld_up(int x, int c) {
if (x == 0) return;
int idx = hidx[x];
auto it = sp.lower_bound(pii(st[x] + 1, 0));
if (hidx[re[it->fs]] == idx) {
gs.emplace_back(it->se, st[x] - max(st[idx] - 1, prev(it)->fs));
}
while (1) {
it = --sp.lower_bound(pii(st[x] + 1, 0));
if (it->fs < st[idx]) break;
gs.emplace_back(it->se, it->fs - max(st[idx] - 1, prev(it)->fs));
sp.erase(it);
}
sp.emplace(st[x], c);
hld_up(par[idx], c);
}
vector<int> cp;
llong fen[100001];
void init(int i) {
while (i <= 100000) {
fen[i] = 0;
i += i & -i;
}
}
void init() {
for (int i : cp) init(i);
cp.clear();
}
void update(int i, int x) {
cp.push_back(i);
while (i <= 100000) {
fen[i] += x;
i += i & -i;
}
}
llong query(int i) {
llong ret = 0;
while (i) {
ret += fen[i];
i -= i & -i;
}
return ret;
}
llong get_ans() {
llong ret = 0;
init();
for (pii i : gs) {
ret += query(i.fs - 1) * i.se;
update(i.fs, i.se);
}
gs.clear();
return ret;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> C[i];
cp.push_back(C[i]);
}
sort(cp.begin(), cp.end());
cp.erase(unique(cp.begin(), cp.end()), cp.end());
for (int i = 1; i <= n; ++i) {
C[i] = lower_bound(cp.begin(), cp.end(), C[i]) - cp.begin() + 1;
}
cp.clear();
for (int i = 1; i < n; ++i) {
cin >> A[i] >> B[i];
par[B[i]] = A[i];
child[A[i]].push_back(B[i]);
}
dfs1(1);
dfs2(1);
sp.emplace(0, 0);
sp.emplace(n + 1, 0);
sp.emplace(st[1], C[1]);
for (int i = 1; i < n; ++i) {
hld_up(B[i], C[B[i]]);
printf("%lld\n", get_ans());
}
return 0;
}
