#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;
inline int read() {
    char c = getchar();
    int x = 0;
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
    return f ? -x : x;
}

void write(lll x) {
	if (x < 0) {
		putchar('-');
		write(-x);
		return;
	}
	if (x > 9) {
		write(x / 10);
	}
	putchar('0' + x % 10);
}

const int maxn = 100100;
const ll inf = 0x3f3f3f3f3f3f3f3fLL;

ll n, a[maxn], head[maxn], len;
lll f[maxn][4];

struct edge {
	int to, next;
} edges[maxn << 1];

void add_edge(int u, int v) {
	edges[++len].to = v;
	edges[len].next = head[u];
	head[u] = len;
}

void dfs(int u, int fa) {
	vector<int> son;
	for (int i = head[u]; i; i = edges[i].next) {
		int v = edges[i].to;
		if (v == fa) {
			continue;
		}
		dfs(v, u);
		son.pb(v);
	}
	lll mx = -inf, val1 = a[u], val2 = -a[u];
	vector<lll> v1, v2;
	for (int v : son) {
		f[u][0] += max({f[v][0], f[v][1], f[v][2]});
		f[u][1] += max({f[v][0], f[v][1], f[v][2]});
		mx = max(mx, f[v][3] - max({f[v][0], f[v][1], f[v][2]}));
		val1 += max({f[v][0], f[v][1], f[v][2]});
		v1.pb(f[v][0] - max({f[v][0], f[v][1], f[v][2]}) - a[v]);
		val2 += max({f[v][0], f[v][1], f[v][2]});
		v2.pb(f[v][0] - max({f[v][0], f[v][1], f[v][2]}) + a[v]);
	}
	sort(v1.begin(), v1.end(), greater<lll>());
	sort(v2.begin(), v2.end(), greater<lll>());
	if (son.size()) {
		val1 += v1[0];
		for (int i = 1; i < (int)v1.size(); ++i) {
			if (v1[i] <= 0) {
				break;
			}
			val1 += v1[i];
		}
		val2 += v2[0];
		for (int i = 1; i < (int)v2.size(); ++i) {
			if (v2[i] <= 0) {
				break;
			}
			val2 += v2[i];
		}
		// printf("val1: ");
		// write(val1);
		// putchar('\n');
		// printf("val2: ");
		// write(val2);
		// putchar('\n');
		f[u][2] = max(val1, val2);
		f[u][3] = max(val1 - a[fa], val2 + a[fa]);
	} else {
		f[u][2] = -inf;
		f[u][3] = abs(a[u] - a[fa]);
	}
	f[u][1] += mx;
	if (son.empty()) {
		f[u][1] = -inf;
	}
	// printf("u: %d ", u);
	// for (int i = 0; i < 4; ++i) {
		// write(f[u][i]);
		// putchar(' ');
	// }
	// putchar('\n');
}

void solve() {
	n = read();
	for (int i = 1; i <= n; ++i) {
		a[i] = read();
	}
	for (int i = 1, u, v; i < n; ++i) {
		u = read();
		v = read();
		add_edge(u, v);
		add_edge(v, u);
	}
	dfs(1, 0);
	write(max({f[1][0], f[1][1], f[1][2]}));
}

int main() {
	// freopen("starfish.in", "r", stdin);
	// freopen("starfish.out", "w", stdout);
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}