#include <bits/stdc++.h>
#define int long long
using namespace std;
int a;
int t[1000005];
vector <int> z[1000005];
int sta[1000005];
int fin[1000005];
int tour;
int par[100005][21];
int rev[1000005];
pair<int,int> edge[100005];
vector<int> v;
vector <int> used;
int fwd[1000005];
void dfs(int i,int parent){
par[i][0]=parent;
tour++;
sta[i]=tour;
rev[tour]=i;
for (auto p:z[i]){
dfs(p,i);
}
fin[i]=tour;
}
pair<int,int> f[4000005];
pair<int,int> combine(pair<int,int> a, pair<int,int> b){
if (a.first>b.first){
return a;
}else{
return b;
}
}
void update(int id,int l,int r,int pos,pair<int,int> val){
if (l==r){
f[id]=val;
return;
}
int mid=(l+r)/2;
if (pos<=mid){
update(id*2,l,mid,pos,val);
}else{
update(id*2+1,mid+1,r,pos,val);
}
f[id]=combine(f[id*2],f[id*2+1]);
}
pair<int,int> get(int id,int l,int r,int x,int y){
if (x>r || y<l){
return {0LL,0LL};
}
if (l>=x && y>=r){
return f[id];
}
int mid=(l+r)/2;
return combine( get(id*2,l,mid,x,y), get(id*2+1,mid+1,r,x,y) );
}
int bit[1000005];
void reset(){
for (auto p:used){
bit[p]=0;
}
used.clear();
}
void update(int i,int val){
i++;
while (i<=a){
if (bit[i]==0){
used.push_back(i);
}
bit[i]+=val;
i+= i&-i;
}
}
int query(int i){
i++;
int res=0;
while (i>0){
res+=bit[i];
i-= i&-i;
}
return res;
}
int get(int l,int r){
if (l>r ){
return 0;
}
return query(r)-query(l-1);
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> a;
for (int i=1;i<=a;i++){
cin >> t[i];
v.push_back(t[i]);
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
for (int i=1;i<=a;i++){
t[i]=lower_bound(v.begin(),v.end(),t[i])-v.begin()+1;
}
for (int i=1;i<a;i++){
int x,y;
cin >> x >> y;
z[x].push_back(y);
edge[i]={x,y};
}
dfs(1,0);
fwd[0]=1;
for (int i=1;i<=20;i++){
fwd[i]=fwd[i-1]*2;
}
for (int j=1;j<=20;j++){
for (int i=1;i<=a;i++){
par[i][j]=par[par[i][j-1]][j-1];
}
}
int cnt=1;
for (int i=tour;i>=1;i--){
int u=rev[i];
pair<int,int> pre={cnt,t[u]};
update(1,1,tour,sta[u],pre);
cnt++;
}
int q=1;
while (q<a){
auto [x,y]=edge[q];
int res=0;
// update(t[y],1);
// cout << get(1,1) << "\n";
int p=x;
auto [id,preval]=get(1,1,tour,sta[p],fin[p]);
// if (q==a-1){
// cout << get(1,1,tour,sta[1],fin[1]).first << get(1,1,tour,sta[1],fin[1]).second << "\n";
// }
// cout << id << " " << preval << "\n";
while (p>0){
// if (q==a-1){
// cout << p << " " << id << " " << preval << "\n";
// }
int p1=p;
int mul=1;
for (int i=20;i>=0;i--){
if (par[p1][i]==0){
continue;
}
pair<int,int> pre=get(1,1,tour,sta[par[p1][i]],fin[par[p1][i]]);
if (pre.first==id){
mul+=fwd[i];
p1=par[p1][i];
}
}
int val=get(1,preval-1);
// cout << p1 << " " << preval << " " << " ok" << "\n";
res+=val*mul;
update(preval,mul);
p=par[p1][0];
pair<int,int> pre=get(1,1,tour,sta[p],fin[p]);
id=pre.first;
preval=pre.second;
}
pair<int,int> pre={q+tour,t[y]};
// cout << y << " ";
update(1,1,tour,sta[y],pre);
cout << res << "\n";
reset();
q++;
}
return 0;
}
