/// In The Name Of God
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define pp pop_back
#define mp make_pair
#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, l, r) for (int i = (l); i >= (r); i--)
#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define nl '\n'
#define ioi exit(0);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int N = (int)1e5 + 7;
const int inf = (int)1e9 + 7;
const int mod = (int)1e9 + 7;
const ll linf = (ll)1e18 + 7;
const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
using namespace std;
int n;
int a[N];
pair <int, int> e[N];
vector <int> g[N];
int sz[N], up[N], par[N], len[N], dep[N];
struct fenwick {
int f[N];
void upd(int p, int x) {
for (; p < N; p |= p + 1) f[p] += x;
}
int get(int p) {
int res = 0;
for (; p >= 0; p = (p & (p + 1)) - 1) res += f[p];
return res;
}
} T;
void dfs_sz(int v = 1, int p = 0) {
sz[v]++;
par[v] = p;
dep[v] = dep[p] + 1;
for (auto &to : g[v]) {
if (to != p) {
dfs_sz(to, v);
sz[v] += sz[to];
if (sz[to] > sz[g[v][0]]) swap(g[v][0], to);
}
}
}
void dfs(int v = 1) {
len[up[v]]++;
for (auto to : g[v]) {
up[to] = (to == g[v][0] ? up[v] : to);
dfs(to);
}
}
vector < pair <int, int > > path[N];
void paint_v(vector < pair <int, int> > &x, int L, int c) {
reverse(all(x));
int add = L;
while (sz(x)) {
auto &it = x.back();
if (it.s <= L) {
L -= it.s;
x.pp();
}
else {
it.s -= L;
break;
}
}
x.pb({c, add});
reverse(all(x));
}
void paint(int v, int x) {
paint_v(path[up[v]], dep[v] - dep[up[v]] + 1, x);
v = par[up[v]];
while (v) {
int cut = dep[v] - dep[up[v]] + 1, L = cut;
reverse(all(path[up[v]]));
while (sz(path[up[v]])) {
auto &it = path[up[v]].back();
if (it.s <= cut) {
cut -= it.s;
path[up[v]].pp();
}
else {
it.s -= cut;
break;
}
}
path[up[v]].pb({x, L});
reverse(all(path[up[v]]));
v = par[up[v]];
}
}
ll inv(vector < pair <int, int > > &x) {
ll sum = 0;
for (auto it : x) {
sum += (ll)(T.get(N - 1) - T.get(it.f)) * it.s;
T.upd(it.f, it.s);
}
for (auto it : x) {
T.upd(it.f, -it.s);
}
return sum;
}
void calc(int v, int u) {
vector < pair <int, int> > s;
int L = dep[v] - dep[up[v]] + 1, V = v;
for (auto it : path[up[v]]) {
if (it.s < L) {
s.pb(it), L -= it.s;
}
else {
s.pb({it.f, L});
break;
}
}
reverse(all(s));
v = par[up[v]];
while (v) {
int need = dep[v] - dep[up[v]] + 1;
vector < pair <int, int > > add;
for (auto it : path[up[v]]) {
if (it.s < need) {
add.pb(it);
need -= it.s;
}
else {
add.pb({it.f, need});
break;
}
}
reverse(all(add));
for (auto it : add) s.pb(it);
v = par[up[v]];
}
reverse(all(s));
ll cnt = inv(s);
/*
rep(i, 0, sz(s) - 1) {
rep(j, i + 1, sz(s) - 1) {
if (s[i].f > s[j].f) cnt += s[i].s * 1ll * s[j].s;
}
}*/
paint(V, a[u]);
if (sz(path[up[u]]) && path[up[u]].back().f == a[u]) {
path[up[u]][sz(path[up[u]]) - 1].s++;
}
else {
path[up[u]].pb({a[u], 1});
}
cout << cnt << nl;
}
int main() {
#ifdef IOI2018
freopen ("in.txt", "r", stdin);
#endif
Kazakhstan
cin >> n;
rep(i, 1, n) cin >> a[i];
rep(i, 2, n) {
cin >> e[i].f >> e[i].s;
g[e[i].f].pb(e[i].s);
}
dfs_sz();
up[1] = 1;
dfs();
{ /// compressing
vector <int> cmp;
rep(i, 1, n) {
cmp.pb(a[i]);
}
sort(all(cmp));
cmp.erase(unique(all(cmp)), cmp.end());
rep(i, 1, n) {
a[i] = lower_bound(all(cmp), a[i]) - cmp.begin();
}
}
rep(i, 2, n) {
calc(e[i].f, e[i].s);
}
ioi
}
