#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define rep(i, a, b) for (int i = a; i <= (b); i++)
#define drep(i, a, b) for (int i = a; i >= (b); i--)
const int maxn = 1e5 + 5;
typedef long long ll;
const ll inf = 1e18;
vector<int> g[maxn];
int p[maxn];
ll dp[maxn][4];
void dfs(int u, int fa) {
	ll d3 = -inf;
	vector<ll> d0, _d0;
	for (auto v : g[u]) {
		if (v == fa)
			continue;
		dfs(v, u);
		ll tmp = max({dp[v][0], dp[v][1], dp[v][2]});
		dp[u][0] += tmp;
		dp[u][1] += tmp;
		d3 = max(d3, dp[v][3] - tmp);
		dp[u][2] += tmp; // 后面部分要换成dp[v][0]，然后在p-Σx里收益是-p[v]，即差值为dp[v][0]-p[v]-tmp(另一个就是+p[v])
		dp[u][3] += tmp;
		d0.push_back(dp[v][0] - p[v] - tmp);
		_d0.push_back(dp[v][0] + p[v] - tmp);
	}
	dp[u][1] += d3;
	ll a = p[u], mx = -inf, b = -p[u], c = p[u] - p[fa], dd = p[fa] - p[u];
	int oka = 0, okb = 0;
	for (auto d : d0) {
		mx = max(mx, d);
		if (d >= 0) {
			c += d;
			a += d;
			oka = 1;
		}
	}
	if (!oka)
		a += mx;
	mx = -inf;
	for (auto d : _d0) {
		mx = max(mx, d);
		if (d >= 0) {
			dd += d;
			b += d;
			okb = 1;
		}
	}
	if (!okb)
		b += mx;
	dp[u][2] += max(a, b);
	dp[u][3] += max(c, dd);
}

signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int n;
	cin >> n;
	rep(i, 1, n) cin >> p[i];
	rep(i, 1, n - 1) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1, 0);
	cout << max({dp[1][0], dp[1][1], dp[1][2]});

	return 0;
}