#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,val[200005],cnt,lst[200005],tot;
struct edge{
	int f,t,lst;
	edge(int f=0,int t=0,int lst=0):
		f(f),t(t),lst(lst){}
}e[400005];
void add(int u,int v){
	e[++cnt]=edge(u,v,lst[u]);lst[u]=cnt;
	e[++cnt]=edge(v,u,lst[v]);lst[v]=cnt;
}
priority_queue<int> q[200005];
void dfs(const int u,const int fa){
	for(int i=lst[u];i;i=e[i].lst){
		int v=e[i].t;
		if(v==fa)continue;
		dfs(v,u);
		if(q[u].size()<q[v].size())swap(q[u],q[v]);
		while(!q[v].empty())q[u].push(q[v].top()),q[v].pop();
	}
	int op=1,now=val[u];
	while(!q[u].empty()){
		if(op==1&&now>=q[u].top())break;
		now+=-op*q[u].top();
		q[u].pop();op*=-1;
	}
	if(op==-1){
		if(n&1)tot-=now;
		else tot+=now;
	}
	else q[u].push(now);
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++)scanf("%lld",&val[i]),tot+=val[i];
	for(int i=1;i<n;i++){
		int u,v;scanf("%lld%lld",&u,&v);
		add(u,v);
	} 
	dfs(1,0);
	int now=1;
	while(!q[1].empty()){
		tot+=now*q[1].top();
		q[1].pop(),now*=-1;
	}
	cout<<tot/2;
	return 0;
}