# include <bits/stdc++.h>
using namespace std;
using ll=long long;
int a[100010],b[100010],ch[100010][2],fa[100010],sz[100010],val[100010],cnt,tot=0;
pair<int,int> c[100010];
namespace BIT
{
	int cnt[100010];
	void update(int x,int y)
	{
		for(int i=x;i<=tot;i+=i&-i) cnt[i]+=y;
	}
	int query(int x)
	{
		int ans=0;
		for(int i=x;i;i-=i&-i) ans+=cnt[i];
		return ans;
	}
}
inline bool Root(int x){return ch[fa[x]][0]!=x && ch[fa[x]][1]!=x;}
inline int get(int x){return ch[fa[x]][1]==x;}
void pushup(int x)
{
	sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;
	val[x]=(ch[x][1]?val[ch[x][1]]:a[x]);
}
void rotate(int x)
{
	int k=get(x),y=fa[x],z=fa[y];
	if(!Root(y)) ch[z][ch[z][1]==y]=x;
	fa[x]=z;
	ch[y][k]=ch[x][k^1];
	if(ch[y][k]) fa[ch[y][k]]=y;
	ch[x][k^1]=y;fa[y]=x;
	pushup(y);pushup(x);
}
void splay(int x)
{
	for(;!Root(x);rotate(x))
		if(!Root(fa[x]))
			rotate(get(x)==get(fa[x])?fa[x]:x);
}
void access(int x)
{
	for(int y=0;x;y=x,x=fa[x])
	{
		splay(x);
		c[++cnt]={val[x],sz[ch[x][0]]+1};
		ch[x][1]=y;pushup(x);
	}
}
int main()
{
	int n,u,v;
	cin>>n;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	memcpy(b+1,a+1,sizeof(int)*n);
	sort(b+1,b+n+1);
	tot=unique(b+1,b+n+1)-b-1;
	auto get=[](int x){return lower_bound(b+1,b+tot+1,x)-b;};
	for(int i=1;i<=n;i++) sz[i]=1,val[i]=a[i]=get(a[i]);
	for(int i=1;i<n;i++)
	{
		ll ans=0;
		scanf("%d%d",&u,&v);fa[v]=u;
		cnt=0;access(v);
		for(int i=2;i<=cnt;i++)
		{
			ans+=(ll)BIT::query(c[i].first-1)*c[i].second;
			BIT::update(c[i].first,c[i].second);
		}
		for(int i=2;i<=cnt;i++) BIT::update(c[i].first,-c[i].second);
		printf("%lld\n",ans);
	}
	return 0;
}