#include <bits/stdc++.h>
using namespace std;

int main() {
	std::ios_base::sync_with_stdio(false);
	int n; cin >> n;
	vector<int64_t> w(n+1);
	int64_t tw = 0;
	for (int i = 1; i <= n; ++i) {
		cin >> w[i]; tw += w[i];
	}
	vector<vector<int>> adj(n+1);
	for (int i = 1; i <= n - 1; ++i) {
		int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u);
	}
	vector<int64_t> pw(n+1);
	vector<pair<int, int>> etime(n+1);
	vector<int> etour;
	function<int64_t(int, int)> dfs1 = [&] (int u, int from) {
		int enter = etour.size();
		etour.push_back(u);
		int64_t ans = w[u];
		for (auto v : adj[u]) if (v != from) ans += dfs1(v, u);
		int left = etour.size();
		etime[u] = {enter, left};
		pw[u] = tw - ans;
		return ans;
	};
	dfs1(1, -1);
	vector<vector<int>> sub(n * 4 + 1);
	auto etour_cmp = [&] (int u, int v) { return pw[u] < pw[v]; };
	function<int(int, int, int)> build = [&] (int l, int r, int k) {
		vector<int>& sorted = sub[k];
		if (r - l > 1) {
			int m = l + (r - l) / 2;
			vector<int>&lsorted = sub[build(l, m, k * 2)];
			vector<int>&rsorted = sub[build(m, r, k * 2 + 1)];
			merge(
				lsorted.begin(), lsorted.end(),
				rsorted.begin(), rsorted.end(),
				back_inserter(sorted), etour_cmp
			);
		} else {
			sorted.insert(sorted.end(), etour.begin()+l, etour.begin()+r);
		}
		return k;
	};
	int k = build(0, etour.size(), 1);
	int64_t ans = 2 * tw; // worst case - triplicate the tree

	function<int(vector<int>&,int)> find_closest_helper = [&] (vector<int>& arr, int64_t hw) {
		int l = 0, r = arr.size();
		int64_t best = -1;
		int best_idx;
		while (l < r) {
			int m = l + (r - l) / 2;
			if (best == -1 || std::abs(2 * pw[arr[m]] - hw) < best) {
				best = std::abs(2 * pw[arr[m]] - hw);
				best_idx = m;
			}
			if (2 * pw[arr[m]] < hw)
				l = m + 1;
			else
				r = m;
		}
		return arr[best_idx];
	};

	function<int(int, int, int64_t, int, int, int)> find_closest = [&] (int l, int r, int64_t hw, int tl, int tr, int tk) {
		l = max(l, tl);
		r = min(r, tr);
		if (l >= r) {
			return -1;
		}
		if (l == tl && r == tr) {
			return find_closest_helper(sub[tk], hw);
		}
		int tm = tl + (tr - tl) / 2;
		int lans = find_closest(l, r, hw, tl, tm, tk * 2);
		int rans = find_closest(l, r, hw, tm, tr, tk * 2 + 1);
		if (lans == -1) return rans;
		if (rans == -1) return lans;
		if (std::abs(2 * pw[lans] - hw) < std::abs(2 * pw[rans] - hw))
			return lans;
		return rans;
	};

	for (int u = 1; u <= n; ++u) {
		// we cut away node u and obtain a tree of weight a and its parent is (tw - a)
		int64_t a = tw - pw[u];

		// now we need to find vertex v such that
		// max(pw[v] - a, tw - pw[v]) is minimal
		// a <= pw[v] <= tw
		// so we need to find v s.t. 2 * pw[v] is closest to (a + tw)

		pair<int, int> atime = etime[u];

		// we ignore all vertices in u subtree
		int v1 = find_closest(0, atime.first, a + tw, 0, etour.size(), 1);
		int v2 = find_closest(atime.second, etour.size(), a + tw, 0, etour.size(), 1);

		auto evaluate = [&] (int v) -> int64_t {
			int64_t b = pw[v] - a;
			int64_t c = tw - a - b;
			return 3 * max(a, max(b, c)) - a - b - c;
		};

		for (auto v : vector<int>{v1, v2}) {
			if (v == -1) continue;
			ans = min(ans, evaluate(v));
		}
	}

	cout << ans << endl;
}