#include<bits/stdc++.h>
#include<bits/extc++.h>
#define inl inline
using namespace std;
typedef long long ll;
const int N=2e5+5,IB=1<<21; char IN[IB],*IS=IN+IB,*IT=IS;
#define gc() (IS==IT&&(IT=IN+fread(IS=IN,1,IB,stdin)),IS==IT?EOF:*IS++)
int n,a[N]; ll an; vector<int> e[N]; __gnu_pbds::priority_queue<ll> q[N];
inl int RD()
{
	int s=0; char c; for(;!isdigit(c=gc()););
	for(;isdigit(c);c=gc()) s=s*10+c-48; return s;
}
inl void DFS(int p,int fr)
{
	for(int v:e[p]) v!=fr&&(DFS(v,p),q[p].join(q[v]),0); ll t=a[p],v=1;
	for(;!q[p].empty()&&(v<1||t<q[p].top());t-=v*q[p].top(),q[p].pop(),v*=-1);
	v<1?(an+=(n&1?-1:1)*t):(q[p].push(t),0);
}
int main()
{
	n=RD(); for(int i=1;i<=n;++i) an+=a[i]=RD();
	for(int x,y,i=n;--i;e[x=RD()].push_back(y=RD()),e[y].push_back(x));
	DFS(1,0); ll v=1; for(;!q[1].empty();an+=v*q[1].top(),q[1].pop(),v*=-1);
	printf("%lld\n",an/2); return 0;
}