#include<bits/stdc++.h>
#define printv(a, b) { \
for(auto pv : a) b << pv << " "; \
b << "\n"; \
}
#define eb emplace_back
#define pob pop_back()
#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
#define lc (2 * id + 1)
#define rc (2 * id + 2)
int n;
vector<int> c, tme;
vector<vector<int>> g;
vector<int> pr;
vector<int> in, out, eu;
int ts = 0;
void init(){
g.resize(n + 1);
pr.resize(n + 1);
c.resize(n + 1);
tme.resize(n + 1);
in.resize(n + 1);
out.resize(n + 1);
eu.resize(n + 1);
}
struct SegmentTree{
vector<int> st;
int argmax(int a, int b){
if(tme[a] >= tme[b]) return a;
else return b;
}
void pull(int id){
st[id] = argmax(st[lc], st[rc]);
}
void build(int L, int R, int id){
if(L == R){
st[id] = L;
return;
}
int M = (L + R) / 2;
build(L, M, lc);
build(M + 1, R, rc);
pull(id);
}
void init(){
st.resize(4 * n);
}
void upd(int x, int L = 1, int R = n, int id = 0){
if(L == R) return;
int M = (L + R) / 2;
if(x <= M) upd(x, L, M, lc);
else upd(x, M + 1, R, rc);
pull(id);
}
int query(int l, int r, int L = 1, int R = n, int id = 0){
if(l <= L && R <= r) return st[id];
int M = (L + R) / 2;
if(r <= M) return query(l, r, L, M, lc);
else if(l > M) return query(l, r, M + 1, R, rc);
else return argmax(query(l, r, L, M, lc), query(l, r, M + 1, R, rc));
}
};
int lowbit(int x){
return x & -x;
}
struct BIT{
vector<ll> bit;
void init(){
bit.resize(n + 1);
}
void modify(int x, ll v){
for(; x < bit.size(); x += lowbit(x)) bit[x] += v;
}
ll query(int x){
ll ans = 0;
for(; x > 0; x -= lowbit(x)) ans += bit[x];
return ans;
}
};
void dfs(int now){
in[now] = ++ts;
eu[ts] = now;
for(int i : g[now]) dfs(i);
out[now] = ts;
}
SegmentTree st;
int getv(int v){
int pos = st.query(in[v], out[v]);
//cerr << "getv " << v << " " << pos << "\n";
return c[eu[pos]];
}
ll calc(int v){
//cerr << "calc " << v << "\n";
vector<int> path;
v = pr[v];
while(true){
path.eb(v);
if(v == 1) break;
v = pr[v];
}
//printv(path, cerr);
BIT bit;
bit.init();
ll ans = 0;
reverse(iter(path));
for(int i : path){
int cv = getv(i);
ans += bit.query(n) - bit.query(cv);
//cerr << "cv " << i << " " << cv << "\n";
bit.modify(cv, 1);
}
//cerr << "ok " << ans << "\n";
return ans;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cerr.tie(0);
cin >> n;
init();
for(int i = 1; i <= n; i++){
cin >> c[i];
}
vector<int> tmp = c;
lsort(tmp);
uni(tmp);
for(int i = 1; i <= n; i++){
c[i] = lower_bound(iter(tmp), c[i]) - tmp.begin();
}
//printv(c, cerr);
vector<int> qry(n + 1);
for(int i = 2; i <= n; i++){
int u, v;
cin >> u >> v;
g[u].eb(v);
pr[v] = u;
qry[i] = v;
}
dfs(1);
st.init();
st.build(1, n, 0);
for(int i = 2; i <= n; i++){
int now = qry[i];
cout << calc(now) << "\n";
tme[in[now]] = i;
st.upd(in[now]);
}
return 0;
}
