#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 100007;
int n,a[N];
vector < int > v[N];
pair < int, int > e[N];
int size_of_subtree[N];
deque < pair < int, int > > d[N];
int chains,chain_of_node[N],head_of_chain[N],index_in_chain[N],parent[N];
int it[N];
int p[N];
map < int, int > code;
int all;
char buff[1<<24],*buffp=buff;
inline void read(int &res) {
res=0;
while(*buffp<48) ++buffp;
while(*buffp>47) res=(res<<3)+(res<<1)+*buffp++-48;
}
inline void update(int pos, int value) {
for(;pos<=all;pos+=pos&(-pos)) it[pos]+=value;
}
inline int query(int pos) {
int ans=0;
for(;pos>=1;pos-=pos&(-pos)) ans+=it[pos];
return ans;
}
inline void dfs(int node) {
size_of_subtree[node]=1;
if(v[node].empty()) return;
int i,max_size=-1,which=-1;
for(i=0;i<(int)(v[node].size());i++) {
dfs(v[node][i]);
size_of_subtree[node]+=size_of_subtree[v[node][i]];
if(size_of_subtree[v[node][i]]>max_size) {
max_size=size_of_subtree[v[node][i]];
which=i;
}
}
swap(v[node][0],v[node][which]);
}
inline void build_hld(int node, int chain, int idx) {
chain_of_node[node]=chain;
index_in_chain[node]=idx;
if(v[node].empty()) return;
int i;
build_hld(v[node][0],chain,idx+1);
for(i=1;i<(int)(v[node].size());i++) {
head_of_chain[++chains]=v[node][i];
build_hld(v[node][i],chains,1);
}
}
inline void append(int chain, int value) {
if(!d[chain].empty() && d[chain].back().first==value) {
++d[chain][d[chain].size()-1].second;
}
else {
d[chain].push_back(make_pair(value,1));
}
}
inline void extract(deque < pair < int, int > > d, int cnt, vector < pair < int, int > > &f) {
int i,from=(int)(f.size()),to=from-1;
for(i=0;i<(int)(d.size()) && cnt>0;i++) {
int curr=min(cnt,d[i].second);
cnt-=curr;
f.push_back(make_pair(d[i].first,curr));
++to;
}
while(from<to) {
swap(f[from++],f[to--]);
}
}
inline long long count_inversions(int node) {
vector < pair < int, int > > v;
long long ans=0;
int i;
while(node) {
extract(d[chain_of_node[node]],index_in_chain[node],v);
node=parent[head_of_chain[chain_of_node[node]]];
}
for(i=0;i<(int)(v.size());i++) {
ans+=query(v[i].first-1)*1ll*v[i].second;
update(v[i].first,v[i].second);
}
for(i=0;i<(int)(v.size());i++) {
update(v[i].first,-v[i].second);
}
return ans;
}
inline void eliminate(deque < pair < int, int > > &d, int cnt) {
while(!d.empty() && cnt>=d.front().second) {
cnt-=d.front().second;
d.pop_front();
}
if(cnt>0) d[0].second-=cnt;
}
inline void assign(int node, int value) {
while(node) {
eliminate(d[chain_of_node[node]],index_in_chain[node]);
if(!d[chain_of_node[node]].empty() && d[chain_of_node[node]].front().first==value) {
d[chain_of_node[node]][0].second+=index_in_chain[node];
}
else {
d[chain_of_node[node]].push_front(make_pair(value,index_in_chain[node]));
}
node=parent[head_of_chain[chain_of_node[node]]];
}
}
int main() {
fread(buff,1,sizeof(buff),stdin);
int i;
read(n);
for(i=1;i<=n;i++) {
read(a[i]);
p[i]=a[i];
}
sort(p+1,p+1+n);
code[p[1]]=1;
for(i=2;i<=n;i++) if(p[i]!=p[i-1]) {
code[p[i]]=code[p[i-1]]+1;
}
all=code[p[n]];
for(i=1;i<=n;i++) {
a[i]=code[a[i]];
}
for(i=1;i<n;i++) {
read(e[i].first);
read(e[i].second);
parent[e[i].second]=e[i].first;
v[e[i].first].push_back(e[i].second);
}
dfs(1);
chains=1;
head_of_chain[1]=1;
build_hld(1,1,1);
append(1,a[1]);
for(i=1;i<n;i++) {
printf("%lld\n", count_inversions(e[i].first));
append(chain_of_node[e[i].second],a[e[i].second]);
assign(e[i].second,a[e[i].second]);
}
return 0;
}
