/* In the name of God, aka Allah */
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
#define mk make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 1e5 + 50, LG = 17;
int n, a[N], f[N], h[N], st[N], ft[N], par[LG][N], fen[2][N], tim;
pii P[N];
pii E[N];
vector<int> adj[N];
void dfs(int u) {
st[u] = ++tim;
for (int v:adj[u]) {
h[v] = h[u]+1;
par[0][v] = u;
dfs(v);
}
ft[u] = tim;
}
int get(int c, int i) {
int out = 0;
for (; i > 0; i -= i&-i) out += fen[c][i];
return out;
}
void upd(int c, int i, int x) {
for (; i <= n; i += i&-i) fen[c][i] += x;
}
int getpar(int u) {
int tmp = get(0, st[u]);
int v = u;
for (int k = LG-1; k >= 0; k--) {
if (tmp - get(0, st[par[k][v]]) == 0) v = par[k][v];
}
return v;
}
void solve() {
cin >> n;
for (int u = 1; u <= n; u++) {
cin >> a[u];
P[u] = {a[u], u};
}
sort(P+1, P+n+1);
int t = 0;
for (int i = 1; i <= n; i++) {
if (P[i].F != P[i-1].F) t++;
a[P[i].S] = t;
}
for (int i = 1; i <= n-1; i++) {
int u, v;
cin >> u >> v;
E[i] = {u, v};
adj[u].push_back(v);
}
h[1] = 1;
dfs(1);
for (int k = 1; k < LG; k++) {
for (int u = 1; u <= n; u++) {
par[k][u] = par[k-1][par[k-1][u]];
}
}
upd(0, st[1], +1);
upd(0, ft[1]+1, -1);
for (int i = 1; i <= n-1; i++) {
int u = E[i].F;
ll out = 0;
while (u) {
int v = getpar(u);
upd(1, a[v], h[u]-h[v]+1);
out += 1ll*(h[u]-h[v]+1)*get(1, a[v]-1);
u = par[0][v];
}
cout << out << endl;
u = E[i].F;
if (f[u]) {
upd(0, st[f[u]], +1);
upd(0, ft[f[u]]+1, -1);
a[f[u]] = a[getpar(u)];
}
f[u] = E[i].S;
while (u) {
int v = getpar(u);
upd(1, a[v], -(h[u]-h[v]+1));
a[v] = a[E[i].S];
if (v != 1) {
upd(0, st[v], -1);
upd(0, ft[v]+1, +1);
upd(0, st[f[par[0][v]]], +1);
upd(0, ft[f[par[0][v]]]+1, -1);
a[f[par[0][v]]] = a[getpar(v)];
f[par[0][v]] = v;
}
u = par[0][v];
}
}
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
solve();
return 0;
}
