#include <bits/stdc++.h>
using namespace std;
int size_ = 1, rems = 1;
int va[1 << 18], vb[1 << 18], dat[1 << 18];
int V[1 << 17][118], VS[1 << 18];
void inits(int sz) {
while (size_ <= sz) size_ *= 2;
int cnt = 1;
for (int i = size_; i >= 1; i /= 2) {
for (int j = 0; j < size_; j += i) {
va[cnt] = j;
vb[cnt] = j + i;
cnt++;
}
}
}
void update(int pos, int x) {
pos += size_;
dat[pos] = x;
while (pos >= 2) {
pos >>= 1;
dat[pos] = max(dat[pos * 2], dat[pos * 2 + 1]);
}
}
int query(int pos) {
int ret = -(1 << 30);
for (int i = 0; i < VS[pos]; i++) ret = max(ret, dat[V[pos][i]]);
return ret;
}
void query_init_(int pos, int l, int r, int a, int b, int u) {
if (l <= a && b <= r) { V[pos][VS[pos]] = u; VS[pos]++; return; }
if (b <= l || r <= a) return;
query_init_(pos, l, r, a, (a + b) >> 1, u * 2);
query_init_(pos, l, r, (a + b) >> 1, b, u * 2 + 1);
}
void query_init(int pos, int l, int r) {
query_init_(pos, l, r, 0, size_, 1);
}
class BIT {
public:
vector<int>bit; int size1_;
void init(int sz) {
size1_ = sz + 2;
bit.resize(size1_ + 1, 0);
}
void add(int pos, int x) {
pos++;
while (pos <= size1_) {
bit[pos] += x; pos += (pos & -pos);
}
}
int sum(int pos) {
int s = 0; pos++;
while (pos >= 1) {
s += bit[pos]; pos -= (pos & -pos);
}
return s;
}
};
long long check_inversions(vector<pair<int, int>> vec) {
vector<int> A;
for (int i = 0; i < (int)vec.size(); i++) A.push_back(vec[i].first);
sort(A.begin(), A.end());
A.erase(unique(A.begin(), A.end()), A.end());
for (int i = 0; i < (int)vec.size(); i++) vec[i].first = lower_bound(A.begin(), A.end(), vec[i].first) - A.begin();
BIT Z; Z.init(A.size() + 1);
long long ans = 0;
for (int i = 0; i < (int)vec.size(); i++) {
ans += 1LL * vec[i].second * (Z.sum(A.size()) - Z.sum(vec[i].first));
Z.add(vec[i].first, vec[i].second);
}
return ans;
}
int N, C[1 << 18], A[1 << 18], B[1 << 18], dist[1 << 18], dp[1 << 18][20];
int cl[1 << 18], cr[1 << 18], cnts;
vector<int> X[1 << 18];
void dfs(int pos, int dep) {
cnts++; cl[pos] = cnts; dist[pos] = dep;
for (int i = 0; i < (int)X[pos].size(); i++) {
if (dist[X[pos][i]] != -1) continue;
dp[X[pos][i]][0] = pos;
dfs(X[pos][i], dep + 1);
}
cr[pos] = cnts;
}
int prevs(int pos, int x) {
for (int i = 19; i >= 0; i--) {
if (x >= (1 << i)) { x -= (1 << i); pos = dp[pos][i]; }
}
if (pos == 0) pos = 1;
return pos;
}
vector<pair<int, int>> get_inverse(int pos) {
vector<pair<int, int>> U;
while (true) {
// Binary Search.
int L = 0, R = dist[pos] + 1, M, maxn = (1 << 30);
int E = query(pos);
for (int i = 0; i < 20; i++) {
M = (L + R) / 2;
int G = prevs(pos, M);
int P = query(G);
if (E != P) { maxn = min(maxn, M); R = M; }
else { L = M; }
}
if (maxn == (1 << 30)) { U.push_back(make_pair(C[B[E]], dist[pos] + 1)); break; }
U.push_back(make_pair(C[B[E]], maxn));
pos = prevs(pos, maxn);
}
reverse(U.begin(), U.end());
return U;
}
int main() {
scanf("%d", &N);
for (int i = 1; i <= N; i++) scanf("%d", &C[i]);
for (int i = 1; i <= N - 1; i++) {
scanf("%d%d", &A[i], &B[i]);
X[A[i]].push_back(B[i]);
X[B[i]].push_back(A[i]);
}
for (int i = 1; i <= N; i++) dist[i] = -1;
dfs(1, 0);
for (int i = 0; i < 19; i++) {
for (int j = 1; j <= N; j++) dp[j][i + 1] = dp[dp[j][i]][i];
}
inits(N + 2);
for (int i = 1; i <= N; i++) query_init(i, cl[i], cr[i] + 1);
update(cl[1], 0);
for (int i = 1; i <= N - 1; i++) {
vector<pair<int, int>> T = get_inverse(A[i]);
printf("%lld\n", check_inversions(T));
update(cl[B[i]], i);
}
return 0;
}
