#ifdef Home
#define _GLIBCXX_DEBUG
#endif // Home
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 100100;
vector < int > adj[N];
int sz[N], head[N], up[N], depth[N], C[N];
deque < pair < int, int > > HLD[N];
vector < pair < int, int > > V, edges;
ll tree[N];
stack < pair < int, int > > st;
void upd(int pos, int val) {
for(; pos < N; tree[pos] += val, pos += -pos&pos);
}
ll sum(int x) {
ll ans = 0;
for(; x; ans += tree[x], x ^= -x&x);
return ans;
}
void dfs(int v) {
if(!head[v]) {
head[v] = v;
}
HLD[head[v]].push_back({C[v], 1});
int mx = 0;
for(auto &u : adj[v]) {
if(!mx || sz[u] > sz[mx]) {
mx = u;
}
}
if(mx) {
head[mx] = head[v];
}
for(auto &u : adj[v]) {
dfs(u);
}
}
ll cnt_inv() {
ll ans = 0;
for(auto &[x, cnt] : V) {
ans += cnt * sum(x - 1);
upd(x, cnt);
}
for(; !V.empty(); V.pop_back()) {
upd(V.back().first, -V.back().second);
}
return ans;
}
void cut(int i, int k, int b) {
for(int t = k; t;) {
if(HLD[i].front().second <= t) {
st.push(HLD[i].front());
t -= st.top().second;
HLD[i].pop_front();
} else {
st.push({HLD[i].front().first, t});
HLD[i].front().second -= t;
t = 0;
}
}
HLD[i].push_front({b, k});
for(; !st.empty(); st.pop()) {
V.push_back(st.top());
}
}
void solve(int x, int y) {
for(y = C[y]; x;) {
cut(head[x], depth[x] - depth[head[x]] + 1, y);
x = up[head[x]];
}
cout << cnt_inv() << '\n';
}
main() {
#ifdef Home
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // Home
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
edges.resize(n);
for(int i = 1; i <= n; ++ i) {
cin >> edges[i - 1].first;
edges[i - 1].second = i;
sz[i] = 1;
}
sort(edges.begin(), edges.end());
for(int i = 0, j = 1; i < n; ++ i) {
j += (i && edges[i - 1].first < edges[i].first);
C[edges[i].second] = j;
}
edges.pop_back();
for(auto &[a, b] : edges) {
cin >> a >> b;
adj[a].push_back(b);
up[b] = a;
depth[b] = depth[a] + 1;
}
for(int i = n - 1; i --> 0;) {
sz[edges[i].first] += sz[edges[i].second];
}
dfs(1);
for(auto &[x, y] : edges) {
solve(x, y);
}
}
