#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;
#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back
bool mini(auto &x, const auto &y) {
if (y < x) {
x = y;
return 1;
}
return 0;
}
bool maxi(auto &x, const auto &y) {
if (y > x) {
x = y;
return 1;
}
return 0;
}
void run();
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
run();
return 0;
}
const int N = (int) 1e5 + 123;
struct F {
int f[N];
void add(int x, int y) {
x++;
for (; x < N; x += x & (-x)) f[x] += y;
}
int get(int i) {
i++;
int res = 0;
for (; i > 0; i -= i & (-i)) res += f[i];
return res;
}
};
int n;
int c[N];
map<int, int> comp;
vector<int> g[N];
struct HLD {
int up, down;
vector<pair<int, int>> st;
void set(int len, int c) {
int alr = 0;
while (sz(st) && st.back().second + alr <= len) {
alr += st.back().second;
st.pop_back();
}
assert(alr <= len);
if (alr < len) {
st.back().second -= (len - alr);
}
st.pb({c, len});
}
};
int ptr;
HLD hld[N];
int id[N];
int depth[N];
int cnt[N];
int p[N];
pair<int, int> q[N];
void precalc(int v) {
cnt[v] = 1;
for (int u : g[v]) {
precalc(u);
cnt[v] += cnt[u];
}
}
void build_hld(int v, int cur = -1) {
if (cur == -1) {
cur = ptr++;
hld[cur].up = v;
}
id[v] = cur;
hld[cur].down = v;
int to = -1;
for (int u : g[v]) {
if (to == -1 || cnt[u] > cnt[to]) {
to = u;
}
}
if (to != -1) {
build_hld(to, cur);
}
for (int u : g[v]) {
if (u != to) {
build_hld(u, -1);
}
}
}
F f;
ll get(int v) {
static vector<pair<int, int>> cool;
cool.clear();
while (v > 0) {
int w = id[v];
int len = depth[v] - depth[hld[w].up] + 1;
int alr = 0;
int ptr = sz(hld[w].st) - 1;
while (ptr >= 0 && hld[w].st[ptr].second + alr <= len) {
alr += hld[w].st[ptr].second;
ptr--;
}
if (alr < len) {
assert(ptr >= 0);
cool.pb({hld[w].st[ptr].first, len - alr});
}
rep(i, ptr + 1, sz(hld[w].st)) {
cool.pb(hld[w].st[i]);
}
v = p[hld[w].up];
}
ll ans = 0;
for (auto &it : cool) {
ans += it.second * f.get(it.first - 1);
f.add(it.first, it.second);
}
for (auto &it : cool) {
f.add(it.first, -it.second);
}
return ans;
}
void set_color(int v, int c) {
while (v > 0) {
int w = id[v];
int len = depth[v] - depth[hld[w].up] + 1;
hld[w].set(len, c);
v = p[hld[w].up];
}
}
void run() {
cin >> n;
rep(i, 1, n + 1) {
cin >> c[i];
comp[c[i]] = 1;
}
{
int ptr = 0;
for (auto &it : comp) {
it.second = ptr++;
}
}
rep(i, 1, n + 1) {
c[i] = comp[c[i]];
}
rep(i, 1, n) {
int a, b;
cin >> a >> b;
g[a].pb(b);
p[b] = a;
depth[b] = depth[a] + 1;
q[i] = {a, b};
}
precalc(1);
build_hld(1);
rep(i, 0, ptr) {
hld[i].st.pb({-1, depth[hld[i].down] - depth[hld[i].up] + 1});
}
set_color(1, c[1]);
rep(i, 1, n) {
cout << get(q[i].first) << "\n";
set_color(q[i].second, c[q[i].second]);
}
}
