#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 5e5 + 5;
int n, a[maxn], ls[maxn], tot;
struct node {
	int l, r, mx, mx1;
};
int rt[maxn];
struct Segtree {
	node tr[maxn * 150];
	int tag[maxn * 150], 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, int 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, int 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, int &res, int mxx, int mxy, int v1, int v2) {
	//	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;
int g[maxn];
vector<int> e[maxn];
void dfs(int u, int fa) {
	int 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);
		rt[u] = tree.mrg(0, n, rt[u], rt[v], g[u], -1e18, -1e18, g[v], s);
		s += g[v];
		rt[u] = tree.modify(0, n, 0, rt[u], g[u]);
	//	cout << u << " " << v << " " << lst << " " << g[u] << " " << tree.query(0, n, 0, rt[u]) << endl;
	}
//	cout << u << " " << g[u] << endl;
}
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 = -1e18;
	dfs(1, 0);
	cout << g[1] << endl;
	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
*/

/tmp/ccAHz52c.o: in function `dfs(long long, long long)':
answer.code:(.text+0x449): relocation truncated to fit: R_X86_64_PC32 against symbol `a' defined in .bss section in /tmp/ccAHz52c.o
answer.code:(.text+0x45c): relocation truncated to fit: R_X86_64_PC32 against symbol `rt' defined in .bss section in /tmp/ccAHz52c.o
answer.code:(.text+0x46e): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/ccAHz52c.o
answer.code:(.text+0x544): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/ccAHz52c.o
/tmp/ccAHz52c.o: in function `Segtree::modify(long long, long long, long long, long long, long long)':
answer.code:(.text._ZN7Segtree6modifyExxxxx[_ZN7Segtree6modifyExxxxx]+0x19f): relocation truncated to fit: R_X86_64_PC32 against symbol `ls' defined in .bss section in /tmp/ccAHz52c.o
/tmp/ccAHz52c.o: in function `Segtree::mrg(long long, long long, long long, long long, long long&, long long, long long, long long, long long)':
answer.code:(.text._ZN7Segtree3mrgExxxxRxxxxx[_ZN7Segtree3mrgExxxxRxxxxx]+0x36d): relocation truncated to fit: R_X86_64_PC32 against symbol `ls' defined in .bss section in /tmp/ccAHz52c.o
/tmp/ccAHz52c.o: in function `main':
answer.code:(.text.startup+0x2b): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/ccAHz52c.o
answer.code:(.text.startup+0x37): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/ccAHz52c.o
answer.code:(.text.startup+0x43): relocation truncated to fit: R_X86_64_PC32 against symbol `a' defined in .bss section in /tmp/ccAHz52c.o
answer.code:(.text.startup+0x4f): relocation truncated to fit: R_X86_64_PC32 against symbol `ls' defined in .bss section in /tmp/ccAHz52c.o
answer.code:(.text.startup+0x76): additional relocation overflows omitted from the output
collect2: error: ld returned 1 exit status