#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << " == " << x << endl
#define el '\n'
typedef long long ll;
const int mod = 1000000007;
const int inf = 2147483647;
const int N = 200020;
void solve()
{
	int n;
	ll sum = 0, ans = 0;
	cin >> n;
	vector<ll> val(n + 1);
	vector<vector<int>> edge(n + 1);
	for (int i = 1; i <= n; i++) {
		cin >> val[i];
		sum += val[i];
	}
	for (int i = 1, x, y; i < n; i++) {
		cin >> x >> y;
		edge[x].push_back(y);
		edge[y].push_back(x);
	}
	function<priority_queue<ll>(int, int)> dfs = [&](int x, int fa) {
		priority_queue<ll> *q = new priority_queue<ll>();
		ll a = val[x];
		for (int to : edge[x]) {
			if (to == fa)
				continue;
			priority_queue<ll> now = dfs(to, x);
			if (q->size() < now.size()) {
				swap(*q, now);
			}
			while (!now.empty()) {
				ll res = now.top();
				now.pop();
				q->push(res);
			}
		}
		/*priority_queue<ll> now = *q;
		debug(x);
		while (!now.empty()) {
			cout << now.top() << " ";
			now.pop();
		}
		cout << endl;*/
		while (1) {
			int siz = (!q->empty()) ? q->size() : 0;
			if (siz <= 1) {
				break;
			}
			int now = q->top();
			if (a >= now) {
				q->push(a);
				return *q;
			}
			ll b = q->top();
			q->pop();
			ll c = q->top();
			q->pop();
			a = a + c - b;
		}
		int siz = (!q->empty()) ? q->size() : 0;
		if (siz == 0) {
			q->push(a);
			return *q;
		}
		ll b = q->top();
		if (a <= b) {
			q->pop();
			if (n % 2 == 0)
				ans += a - b;
			else
				ans -= a - b;
			return *q;
		}
		q->push(a);
		return *q;
	};
	priority_queue<ll> q = dfs(1, 0);
	int tmp = 0;
	while (!q.empty()) {
		if ((tmp++) % 2 == 0)
			ans += q.top();
		else
			ans -= q.top();
		q.pop();
	}
	cout << (ans + sum) / 2 << endl;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int T = 1;
	// cin>>T;
	while (T--) {
		solve();
	}
	return 0;
}