#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 5;
int n, a[maxn], ls[maxn], tot;
struct node {
	int l, r;
	__int128 mx, mx1;
};
int rt[maxn];
struct Segtree {
	node tr[maxn * 50];
	__int128 tag[maxn * 50], tot;
	void pushup(int t) {
		tr[t].mx = max(tr[tr[t].l].mx, tr[tr[t].r].mx);
		tr[t].mx1 = max(tr[tr[t].l].mx1, tr[tr[t].r].mx1);
	}
	void addtag(int t, __int128 val) {
		tr[t].mx += val;
		tr[t].mx1 += val;
		tag[t] += val;
	}
	void pushdown(int t) {
		if(tr[t].l)
			addtag(tr[t].l, tag[t]);
		if(tr[t].r)
			addtag(tr[t].r, tag[t]);
		tag[t] = 0;
	}
	int modify(int l, int r, int pos, int t, __int128 val) {
		if(!t)
			t = ++tot;
		if(l == r) {
			tr[t].mx = val;
			tr[t].mx1 = val + ls[l];
			return t;
		}
		pushdown(t);
		int mid = l + r >> 1;
		if(pos <= mid)
			tr[t].l = modify(l, mid, pos, tr[t].l, val);
		else
			tr[t].r = modify(mid + 1, r, pos, tr[t].r, val);
		pushup(t);
		return t;
	}
	int mrg(int l, int r, int x, int y, __int128 &res, __int128 mxx, __int128 mxy, __int128 v1, __int128 v2) {
//		if(v1 < 0 || v2 < 0)
//			exit(1);
//		if(x && tr[x].mx < 0)
//			exit(1);
//		if(y && tr[y].mx < 0)	
//			exit(1);
	//	cout << l << " " << r << " " << mxx << " " << mxy << " " << tr[x].mx << " " << tr[y].mx << endl;
		if(!x) {
			res = max(res, tr[y].mx1 + mxx);
			addtag(y, v2);
			return y;
		}
		if(!y) {
			res = max(res, tr[x].mx1 + mxy);
			addtag(x, v1);
			return x;
		}
		if(l == r) {
			res = max(res, max(max(mxx + tr[y].mx, mxy + tr[x].mx), tr[x].mx + tr[y].mx) + ls[l]);
			tr[x].mx = max(tr[x].mx + v1, tr[y].mx + v2);
			tr[x].mx1 = tr[x].mx + ls[l];
			return x;
		}
		int mid = l + r >> 1;
		pushdown(x), pushdown(y);
		tr[x].l = mrg(l, mid, tr[x].l, tr[y].l, res, max(mxx, tr[tr[x].r].mx), max(mxy, tr[tr[y].r].mx), v1, v2);
		tr[x].r = mrg(mid + 1, r, tr[x].r, tr[y].r, res, mxx, mxy, v1, v2);
		pushup(x);
		return x;
	}
	int query(int l, int r, int pos, int t) {
		if(l == r)
			return tr[t].mx;
		int mid = l + r >> 1;
		pushdown(t);
		if(pos <= mid)
			return query(l, mid, pos, tr[t].l);
		else
			return query(mid + 1, r, pos, tr[t].r);
	}
} tree;
__int128 g[maxn], sum[maxn];
vector<int> e[maxn];
void dfs(int u, int fa) {
	sum[u] = ls[a[u]];
	__int128 s = 0;
	rt[u] = tree.modify(0, n, a[u], rt[u], 0);
	tree.modify(0, n, 0, rt[u], 0);
	for (int i = 0; i < e[u].size(); i++) {
		int v = e[u][i];
		if(v == fa)
			continue;
		dfs(v, u);
		if(sum[u] < 0)
			exit(1);
		if(s > sum[u])
			exit(1);
		rt[u] = tree.mrg(0, n, rt[u], rt[v], g[u], (__int128)(-1e15), (__int128)-1e15, g[v], s);
		s += g[v];
		rt[u] = tree.modify(0, n, 0, rt[u], g[u]);
		sum[u] += sum[v];
	//	cout << u << " " << v << " " << lst << " " << g[u] << " " << tree.query(0, n, 0, rt[u]) << endl;
	}
//	cout << u << " " << g[u] << endl;
}
void write(__int128 x) {
	if(x <= 9) {
		putchar(x + '0');
		return ;
	}
	write(x / 10);
	putchar(x % 10 + '0');
}
signed main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i], ls[i] = a[i];
	sort(ls + 1, ls + n + 1);
	for (int i = 1; i <= n; i++)
		a[i] = lower_bound(ls + 1, ls + n + 1, a[i]) - ls;
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	tree.tr[0].mx = tree.tr[0].mx1 = -1e15;
	dfs(1, 0);
	write(g[1]), putchar('\n');
	return 0;
}
/*
8
2 5 4 5 3 1 1 3
1 2
1 3
1 4
2 5
2 6
3 7
4 8
*/