#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define mp make_pair
#define pb push_back
#define ld long double
#define ss(x) (int) x.size()
#define FOR(i, n) for(int i = 1; i <= n; ++i)
#define fi first
#define se second
#define cat(x) cerr << #x << " = " << x << endl;
using namespace std;
using namespace __gnu_pbds;
// order_by_key
// find_by_order
// tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> siema;
const int nax = 100005, pod = (1 << 17);
int n, a, b;
vector <int> v[nax];
int val[nax];
int q[nax][2], h[nax];
int in[nax], fre = 1, out[nax];
int P[nax];
void dfs(int u, int p) {
in[u] = fre++;
for(auto it: v[u]) {
if(it != p) {
P[it] = u;
h[it] = h[u] + 1;
dfs(it, u);
}
}
out[u] = fre;
}
int up[nax];
struct drzewo {
pair<int, int> d[2 * pod];
void init() {
for(int i = 0; i < 2 * pod; ++i)
d[i] = mp(0, 0);
}
void add(int pos, int u, int ile) {
d[pos + pod] = mp(ile, u);
pos += pod;
pos /= 2;
while(pos) {
d[pos] = max(d[2 * pos], d[2 * pos + 1]);
pos /= 2;
}
}
pair<int, int> maxi(int l, int r) {
pair <int, int> res = mp(0, 0);
for(l += pod, r += pod; l < r; l /= 2, r /= 2) {
if(l & 1)
res = max(res, d[l++]);
if(r & 1)
res = max(res, d[--r]);
}
return res;
}
};
struct fen {
int d[nax];
void init() {
for(int i = 0; i < nax; ++i)
d[i] = 0;
}
void add(int pos, int x) {
for(; pos < nax; pos += pos & -pos) {
d[pos] += x;
}
}
int daj(int x) {
int res = 0;
for(; x > 0; x -= x & -x) {
res += d[x];
}
return res;
}
};
fen F;
drzewo D;
vector <pair<int, int>> mam;
vector <int> war;
ll akt(int u) {
mam.clear();
int ans = 0;
while(u != 0 && D.maxi(in[u], out[u]).fi == 0) {
ans += F.daj(val[u] - 1);
F.add(val[u], 1);
mam.pb(mp(val[u], -1));
u = P[u];
}
while(u != 0) {
int color = D.maxi(in[u], out[u]).se;
int ile = h[u] - h[up[color]];
ans += (ll) F.daj(val[color] - 1) * ile;
F.add(val[color], ile);
mam.pb(mp(val[color], -ile));
int D = up[color];
up[color] = u;
u = D;
}
for(auto it: mam)
F.add(it.fi, it.se);
return ans;
}
int main() {
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
F.init();
D.init();
h[0] = -1;
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
scanf("%d", &val[i]);
war.pb(val[i]);
}
sort(war.begin(), war.end());
for(int i = 1; i <= n; ++i)
val[i] = lower_bound(war.begin(), war.end(), val[i]) - war.begin() + 1;
for(int i = 1; i <= n - 1; ++i) {
scanf("%d%d", &q[i][0], &q[i][1]);
v[q[i][0]].pb(q[i][1]);
v[q[i][1]].pb(q[i][0]);
}
dfs(1, 0);
for(int i = 1; i < n; ++i) {
printf("%lld\n", akt(q[i][0]));
D.add(in[q[i][1]], q[i][1], i);
}
return 0;
}
