//https://oj.uz/problem/view/JOI18_construction
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define REP(i, a) for (int i = 0; i < (a); ++i)
#define DEBUG(x) { cerr << #x << '=' << x << endl; }
#define Arr(a, l, r) { cerr << #a << " = {"; FOR(_, l, r) cerr << ' ' << a[_]; cerr << "}\n"; }
#define N 100100
#define pp pair<int, int>
#define endl '\n'
#define IO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define taskname ""
#define bit(S, i) (((S) >> (i)) & 1)
using namespace std;
int n, u[N], v[N], p[N], d[N], c[N], nChild[N], head[N];
vector<int> e[N];
void dfs(int u) {
nChild[u] = 1;
for (int v : e[u]) {
p[v] = u;
d[v] = d[u] + 1;
dfs(v);
nChild[u] += nChild[v];
}
}
void hld(int u) {
if (head[u] == 0) head[u] = u;
int mx = 0, special = -1;
for (int v : e[u]) {
if (mx < nChild[v]) {
special = v; mx = nChild[v];
}
}
for (int v : e[u]) {
if (v == special) head[v] = head[u];
else head[v] = v;
hld(v);
}
}
long long BIT[N];
long long GetBIT(int u) {
long long ans = 0;
for (; u > 0; u -= u & -u) ans += BIT[u];
return ans;
}
void UpBIT(int u, long long val) {
for (; u <= n; u += u & -u) BIT[u] += val;
}
struct Data {
int depth, val, cnt;
};
deque<Data> deq[N];
long long Query(int u) {
long long ans = 0;
vector<pp> history;
while (u) {
int id = head[u];
vector<Data> temp;
int depth = d[u];
while (!deq[id].empty() && deq[id].back().depth < depth) {
temp.push_back(deq[id].back());
deq[id].pop_back();
}
if (!deq[id].empty()) {
Data t = deq[id].back(); deq[id].pop_back();
int newCnt = t.depth - depth;
t.cnt -= newCnt;
temp.push_back(t);
t.cnt = newCnt;
if (t.cnt) deq[id].push_back(t);
}
while (!temp.empty()) {
Data t = temp.back(); temp.pop_back();
ans += 1ll * t.cnt * GetBIT(t.val - 1);
UpBIT(t.val, t.cnt);
history.push_back(pp(t.val, t.cnt));
}
u = p[head[u]];
}
for (pp x : history) UpBIT(x.first, -x.second);
return ans;
}
void Update(int u) {
Data x;
x.val = c[u];
while (u) {
int id = head[u];
x.depth = d[u];
x.cnt = d[u] - d[p[head[u]]];
// DEBUG(deq[id].size());
deq[id].push_back(x);
u = p[head[u]];
}
}
int ranking[N];
int main() {
#ifdef NERO
freopen("test.inp","r",stdin);
freopen("test.out","w",stdout);
double stime = clock();
#else
//freopen(taskname".inp","r",stdin);
//freopen(taskname".out","w",stdout);
#endif //NERO
IO;
cin >> n;
FOR(i, 1, n) cin >> c[i];
FOR(i, 1, n) ranking[i] = c[i];
sort(ranking + 1, ranking + n + 1);
FOR(i, 1, n) {
c[i] = lower_bound(ranking + 1, ranking + n + 1, c[i]) - ranking;
}
FOR(i, 2, n) {
cin >> u[i] >> v[i];
e[u[i]].push_back(v[i]);
}
d[1] = 1;
dfs(1);
hld(1);
FOR(i, 2, n) {
cout << Query(u[i]) << '\n';
Update(v[i]);
}
#ifdef NERO
double etime = clock();
cerr << "Execution time: " << (etime - stime) / CLOCKS_PER_SEC * 1000 << " ms.\n";
#endif // NERO
}
