#include <stdio.h>
#define N 100100
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int aa[N], n;
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k)
if (aa[ii[j]] == aa[i_])
j++;
else if (aa[ii[j]] < aa[i_]) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
sort(ii, l, i);
l = k;
}
}
int ft[N];
void update(int i, int x) {
while (i <= n) {
ft[i] += x;
i |= i + 1;
}
}
int query(int i) {
int x = 0;
while (i >= 0) {
x += ft[i];
i &= i + 1, i--;
}
return x;
}
int pp[N], tt[N][2], sz[N];
int dir(int u) {
return tt[pp[u]][0] == u ? 0 : 1;
}
int isroot(int u) {
return tt[pp[u]][dir(u)] != u;
}
void pul(int u) {
sz[u] = sz[tt[u][0]] + sz[tt[u][1]] + 1;
}
void attach(int p, int u, int d) {
pp[u] = p;
if (p)
tt[p][d] = u, pul(p);
}
void rotate(int u) {
int v = pp[u], w = pp[v], du = dir(u), dv = dir(v), is = isroot(v);
attach(v, tt[u][du ^ 1], du), attach(u, v, du ^ 1);
if (is)
pp[u] = w;
else
attach(w, u, dv);
}
void splay(int u) {
while (!isroot(u)) {
int v = pp[u];
if (isroot(v))
rotate(u);
else
rotate(dir(u) == dir(v) ? v : u), rotate(u);
}
}
int root(int u) {
return isroot(u) ? u : root(pp[u]);
}
int aa_[N], kk_[N], n_;
void expose(int u) {
int v, w;
n_ = 0;
for (v = u, w = 0; v; w = v, v = pp[v]) {
int a, k;
a = aa[root(v)];
splay(v);
k = sz[tt[v][0]] + 1;
aa_[n_] = a, kk_[n_] = k, n_++;
aa[tt[v][1]] = a;
attach(v, w, 1);
}
splay(u);
}
long long solve() {
int i;
long long ans;
ans = 0;
for (i = 0; i < n_; i++) {
ans += (long long) query(aa_[i] - 1) * kk_[i];
update(aa_[i], kk_[i]);
}
for (i = 0; i < n_; i++)
update(aa_[i], -kk_[i]);
return ans;
}
int main() {
static int ii[N];
int h, i, j, a;
scanf("%d", &n);
for (i = 1; i <= n; i++)
scanf("%d", &aa[i]);
for (i = 0; i <= n; i++)
ii[i] = i;
sort(ii, 0, n + 1);
for (i = 0, a = 0; i <= n; i++)
aa[ii[i]] = i == n || aa[ii[i + 1]] != aa[ii[i]] ? a++ : a;
sz[1] = 1;
for (h = 0; h < n - 1; h++) {
scanf("%d%d", &i, &j);
expose(i);
attach(j, i, 0);
printf("%lld\n", solve());
}
return 0;
}
