#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N=1e5+5;

int c[N],fa[N],sz[N],son[N],dfsn[N],point[N],num[N],a[N],top[N],x[N],y[N],n,m,sumroll,cnt;
pair <int,int> roll_back[N];
vector <int> g[N];

struct node
{
	int l,r,min,max,cover;
}res[N*4];

void update(int x,int y)
{
	for(int i=x;i<=m;i+=i&-i)
		c[i] += y;
}

int query(int x)
{
	int ans=0;
	for(int i=x;i;i-=i&-i)
		ans += c[i];
	return ans;
}

void dfs1(int x)
{
	sz[x]=1;
	for(int i=0;i<g[x].size();i++)
	{
		int to=g[x][i];
		if(to==fa[x])
			continue;

		fa[to]=x;
		dfs1(to);
		sz[x] += sz[to];
		if(sz[to]>sz[son[x]])
			son[x]=to;
	}
}

void dfs2(int x,int t)
{
	dfsn[x]=++cnt, top[x]=t, point[cnt]=x;
	if(son[x])
		dfs2(son[x],t);

	for(int i=0;i<g[x].size();i++)
	{
		int to=g[x][i];
		if(to==fa[x] || to==son[x])
			continue;

		dfs2(to,to);
	}
}

void cover(int rt,int val)
{
	res[rt].min=res[rt].max=res[rt].cover=val;
}

void pushup(int rt)
{
	res[rt].min=min(res[rt*2].min,res[rt*2+1].min);
	res[rt].max=max(res[rt*2].max,res[rt*2+1].max);
}

void pushdown(int rt)
{
	if(res[rt].cover)
	{
		cover(rt*2,res[rt].cover);
		cover(rt*2+1,res[rt].cover);
		res[rt].cover=0;
	}
}

void build(int rt,int l,int r)
{
	res[rt].l=l,res[rt].r=r;
	if(l==r)
	{
		res[rt].min=res[rt].max=a[point[l]];
		return;
	}

	int mid=(l+r)/2;
	build(rt*2,l,mid);
	build(rt*2+1,mid+1,r);
	pushup(rt);
}

void update(int rt,int l,int r,int val)
{
	if(l<=res[rt].l && res[rt].r<=r)
	{
		cover(rt,val);
		return;
	}

	pushdown(rt);
	int mid=(res[rt].l+res[rt].r)/2;
	if(l<=mid)
		update(rt*2,l,r,val);
	if(mid+1<=r)
		update(rt*2+1,l,r,val);
	pushup(rt);
}

int query_val(int rt,int pos)
{
	if(res[rt].l==res[rt].r)
		return res[rt].min;

	pushdown(rt);
	int mid=(res[rt].l+res[rt].r)/2;
	if(pos<=mid)
		return query_val(rt*2,pos);
	return query_val(rt*2+1,pos);
}

int query_last(int rt,int r,int val)
{
	if(res[rt].min==val && res[rt].max==val)
		return -1;

	if(res[rt].l==res[rt].r)
		return res[rt].l;

	pushdown(rt);
	if(res[rt*2+1].l>r)
		return query_last(rt*2,r,val);

	int rans=query_last(rt*2+1,r,val);
	if(rans==-1)
		return query_last(rt*2,r,val);
	return rans;
}

void update_path(int x,int y)
{
	while(x)
	{
		update(1,dfsn[top[x]],dfsn[x],y);
		x=fa[top[x]];
	}
}

long long query_path(int x)
{
	if(x==0)
		return 0;

	int val=query_val(1,dfsn[x]), pos=query_last(1,dfsn[x],query_val(1,val));
	if(pos==-1)
		pos=dfsn[top[x]];

	long long ans=1ll*query(val-1)*(dfsn[x]-pos+1);
	update(val,dfsn[x]-pos+1);
	roll_back[++sumroll]=make_pair(val,dfsn[x]-pos+1);
	if(pos==dfsn[top[x]])
		return ans+query_path(fa[top[x]]);
	return ans+query_path(point[pos-1]);
}

void clear()
{
	for(int i=1;i<=sumroll;i++)
		update(roll_back[i].first,-roll_back[i].second);
	sumroll=0;
}

int main()
{
	cin >> n;
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);

	for(int i=1;i<=n;i++)
		num[++m]=i;

	sort(num+1,num+m+1);
	m=unique(num+1,num+m+1)-num-1;
	for(int i=1;i<=n;i++)
		a[i]=lower_bound(num+1,num+m+1,a[i])-num;

	for(int i=1;i<n;i++)
	{
		scanf("%d %d",&x[i],&y[i]);
		g[x[i]].push_back(y[i]);
		g[y[i]].push_back(x[i]);
	}

	dfs1(1);
	dfs2(1,1);
	build(1,1,n);
	for(int i=1;i<n;i++)
	{
		printf("%lld\n",query_path(x[i]));
		update_path(x[i],a[y[i]]);
		clear();
	}
	return 0;
}