#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define x first
#define y second

using namespace std;

typedef long double ld;
typedef long long ll;

vector <int> g[100005];
int metka[100005], value[100005];
multiset <ll> opa[100005];
ll DODIK = 0;

void dfs(int v, int pr)
{
	bool leaf = true;
	for (int u : g[v])
	{
	 	if (u == pr) continue;
	 	dfs(u, v);
	 	leaf = false;
	}

	if (leaf)
	{
	 	metka[v] = v;
	 	opa[v].insert(value[v]);
	 	return;
	}

	int mx = 0;
	for (int u : g[v])
	{
		if (u == pr) continue;
		if (mx == 0 || opa[metka[u]].size() > opa[metka[mx]].size()) mx = u; 	
	}
	metka[v] = metka[mx];

	for (int u : g[v])
	{
	 	if (u == pr || u == mx) continue;
	 	for (ll weight : opa[metka[u]]) opa[metka[v]].insert(weight);
	}

	int sign = -1;
	ll root = value[v];
	while (!opa[metka[v]].empty())
	{
	 	ll last = *opa[metka[v]].rbegin();
	 	if (last <= root) break;

	 	opa[metka[v]].erase(opa[metka[v]].find(last));
	 	root += sign * last;
	 	sign = -sign;
	}
	if (sign == 1) DODIK += root;
	else opa[metka[v]].insert(root);
	return;
}

int main()
{
 	//freopen("input.txt", "r", stdin);
 	//freopen("output.txt", "w", stdout);
	ios_base::sync_with_stdio(0); cin.tie(0);

	int n;
	cin >> n;

	ll sum = 0;
	for (int i = 1; i <= n; i++)
	{
		cin >> value[i];
		sum += value[i];
	}

	for (int i = 1; i < n; i++)
	{
	 	int u, v;
	 	cin >> u >> v;
	 	g[u].pb(v);
	 	g[v].pb(u);
	}
	dfs(1, -1);
 
  	if (n % 2 == 1) DODIK = -DODIK;
	int sign = 1;
	for (auto it = opa[metka[1]].rbegin(); it != opa[metka[1]].rend(); it++)
	{
	 	DODIK += sign * (*it);
	 	sign = -sign;
	}
	cout << (sum + DODIK) / 2 << '\n';
	return 0;
}