#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

typedef long long i64;

const int N = 200005;
int n, a[N];
priority_queue<i64> q[N];
i64 sum;
vector<int> to[N];

void dfs(int i, int fa) {
	for (int j : to[i]) {
		if (j == fa) {
			continue;
		}

		dfs(j, i);
		if (q[i].size() < q[j].size()) {
			swap(q[i], q[j]);
		}
		while (!q[j].empty()) {
			q[i].push(q[j].top());
			q[j].pop();
		}
	}

	i64 tp = a[i];
	while (1) {
		if (q[i].empty() || tp >= q[i].top()) {
			q[i].push(tp);
			return;
		}

		if (q[i].size() == 1) {
			sum += tp - q[i].top();
			q[i].pop();
			return;
		}

		tp -= q[i].top(), q[i].pop();
		tp += q[i].top(), q[i].pop();
	}
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i != n; i++) {
		int x, y;
		cin >> x >> y;
		to[x].push_back(y), to[y].push_back(x);
	}

	dfs(1, 0);

	i64 ans = (q[1].size() & 1) ? -sum : sum;
	bool op = 0;
	while (!q[1].empty()) {
		if (!op) {
			ans += q[1].top();
		} else {
			ans -= q[1].top();
		}
		q[1].pop();
		op ^= 1;
	}

	for (int i = 1; i <= n; i++) {
		ans += a[i];
	}

	cout << ans / 2 << endl;
}