#include<bits/stdc++.h>
using namespace std;
int n,head[100005],tot,x,y,ind,oo;
long long a[100005],sum[100005],dp[100005],cnt[100005],tmpp;
struct stu{
	int to;
	int nxt;
}w[400005];
struct stuu{
	long long val;
	int indd;
}tmp[100005];
bool cmp(stuu aa,stuu bb){
	return aa.val>bb.val;
}
void ade(int xx,int yy){
	w[++tot].to=yy;
	w[tot].nxt=head[xx];
	head[xx]=tot;
}
void dfss(int cyf,int fa){
	sum[cyf]=a[cyf];
	for(int i=head[cyf];i;i=w[i].nxt){
		if(w[i].to==fa)
			continue;
		cnt[cyf]++;
		dfss(w[i].to,cyf);
		sum[cyf]+=sum[w[i].to];
	}
}
void dfs(int cyf,int fa){
	if(cnt[cyf]==0)
		dp[cyf]=a[cyf];
	else{
		for(int i=head[cyf];i;i=w[i].nxt){
			if(w[i].to==fa)
				continue;
			dfs(w[i].to,cyf);
		}
		dp[cyf]=a[cyf];
		ind=0;
		for(int i=head[cyf];i;i=w[i].nxt){
			if(w[i].to==fa)
				continue;
			tmp[++ind].val=dp[w[i].to];
			tmp[ind].indd=w[i].to;
		}
		sort(tmp+1,tmp+1+ind,cmp);
		oo=0;
		for(int i=1;i<=ind;i++){
			if(oo==0)
				tmpp=sum[tmp[i].indd]-tmp[i].val;
			else
				tmpp=tmp[i].val;
			dp[cyf]+=tmpp;
			oo^=1;
		}
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<n;i++){
		cin>>x>>y;
		ade(x,y);
		ade(y,x);
	}
	dfss(1,-1);
	dfs(1,-1);
	cout<<dp[1]<<endl;
	return 0;
}