#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const int N=2e6+1;
int n;
ll a[N];
ll s=0;
vector<int>adj[N];
set<int>luv[N];
ll ans=0;
void dfs(int id,int p){
	int bc=0;
	for(auto c:adj[id]){
		if(c==p) continue;
		dfs(c,id);
		if(luv[c].size()>luv[bc].size()) bc=c;
	}
	if(bc!=0){
		for(auto c:adj[id]){
			if(c==p || c==bc) continue;
			for(auto d:luv[c]) luv[bc].insert(c);
			luv[c].clear();
		}
		swap(luv[bc],luv[id]);
	}
	while(!luv[id].empty() && *luv[id].rbegin()>=a[id]){
		if(luv[id].size()==1){
			ll evil=*luv[id].rbegin()-a[id];
			if(n%2==1) ans+=evil;
			else ans-=evil;
		}
		else{
			a[id]-=*luv[id].rbegin();
			auto it=luv[id].end();--it;luv[id].erase(it);
			a[id]+=*luv[id].rbegin();
			it=luv[id].end();--it;luv[id].erase(it);
		}
	}
	luv[id].insert(a[id]);
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cin >> n;
	for(int i=1; i<=n ;i++){
		cin >> a[i];
		s+=a[i];
	}
	for(int i=1; i<n ;i++){
		int u,v;cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(1,0);
	int sgn=1;
	while(!luv[1].empty()){
		ans+=*luv[1].rbegin()*sgn;
		sgn*=-1;
		auto it=luv[1].end();--it;luv[1].erase(it);
	}
	cout << (ans+s)/2 << '\n';
}