#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
const int N = 1<<17;
vector<int> nei[N];
vector<pair<int, int>> vec[N];
int ft[N], cl[N], tp[N], ch[N], Par[N], hei[N], a[N], b[N];
map<int, int> mp, mp2;
void Add(int i, int v){
for (; i < N; i += i & -i)
ft[i] += v;
}
int get(int i, int ans = 0){
for (; i ; i -= i & -i)
ans += ft[i];
return ans;
}
void dfs(int u,int id = 0){
ch[u] = 1;
for (int i : nei[u]){
Par[i] = u, hei[i] = hei[u] + 1;
dfs(i);
ch[u] += ch[i];
if (ch[i] > ch[nei[u][0]])
swap(nei[u][id], nei[u][0]);
tp[i] = i;
id++;
}
}
void dfs2(int u){
if (nei[u].size() > 0)
tp[nei[u][0]] = tp[u];
for (int i : nei[u])
dfs2(i);
}
int clac_and_upd(int u, int vr){
vector<pair<int, int>> temp, Now;
while (u){
int t = tp[u], sz2 = hei[u] - hei[t] + 1, sz = sz2, k = 0;
while (sz){
if (vec[t].back().second > sz){
temp.push_back({vec[t].back().first, sz});
vec[t].back().second -= sz;
sz = 0;
}
else{
sz -= vec[t].back().second;
temp.push_back(vec[t].back());
vec[t].pop_back();
}
}
vec[t].push_back({cl[vr], sz2 + (tp[vr] == t)});
u = Par[t];
for (int i=temp.size()-1; i >= 0;i--)
Now.push_back(temp[i]);
vector<pair<int,int>> ().swap(temp);
}
long long Ans = 0;
for (auto [c, cnt] : Now){
Ans += 1LL * get(c-1) * cnt;
Add(c, cnt);
}
for (auto [c, cnt] : Now)
Add(c, -cnt);
return Ans;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL);
int n, cur = 0;
cin>>n;
for (int i=1;i<=n;i++)
cin>>cl[i], mp[cl[i]];
for (auto [i, j] : mp)
mp2[i] = ++cur;
for (int i=1;i<=n;i++)
cl[i] = mp2[cl[i]];
for (int i=1;i<n;i++){
cin>>a[i]>>b[i];
nei[a[i]].push_back(b[i]);
}
dfs(1);
dfs2(tp[1] = 1);
vec[1].push_back({cl[1], 1});
for (int i=1;i<n;i++){
cout<<clac_and_upd(a[i], b[i])<<endl;
if (tp[b[i]] == b[i])
vec[b[i]].push_back({cl[b[i]], 1});
}
}
