#include <bits/stdc++.h>

using namespace std;

namespace FastRead{
	char buf[1000005], *s = buf, *t = buf, ch, f;
	#define gc() s == t && (t = (s = buf) + fread(buf, 1, 1000000, stdin), s == t) ? EOF : *s ++ 
	template <typename T>
	inline void Read(T &x)
	{
		x = f = 0, ch = gc();
		while(ch < '0' || ch > '9')
		{
			if(ch == '-') f = 1;
			ch = gc();
		}
		while('0' <= ch && ch <= '9') x = x * 10 + ch - 48, ch = gc();
		f && (x = -x);
	}
};
using FastRead::Read;

typedef long long LL;

const int N = 5e5 + 5;

int n;
int a[N], xx[N], s;
int la[N], ne[N * 2], en[N * 2], idx;
struct Node{
	int l, r;
	LL v0, v1, t;
}t[N << 5];
int rt[N], pid;

#define mid ((a + b) >> 1)
inline void PushUp(int u)
{
	t[u].v0 = max(t[t[u].l].v0, t[t[u].r].v0);
	t[u].v1 = max(t[t[u].l].v1, t[t[u].r].v1);
}
inline void Change(int u, LL d)
{
	u && (t[u].v0 += d, t[u].v1 += d, t[u].t += d);
}
inline void PushDown(int u)
{
	if(t[u].t)
	{
		Change(t[u].l, t[u].t);
		Change(t[u].r, t[u].t);
		t[u].t = 0;
	}
}
inline void Insert(int &u, int x, LL d, int a = 1, int b = s)
{
	if(!u) u = ++ pid;
	t[u].v0 = max(t[u].v0, d);
	t[u].v1 = max(t[u].v1, d + xx[x]);
	if(a == b) return ;
	PushDown(u);
	if(x <= mid) Insert(t[u].l, x, d, a, mid);
	else Insert(t[u].r, x, d, mid + 1, b);
}
inline void Query0(int u, int x, LL &f, int a = 1, int b = s)
{
	if(!u) return ;
	if(a == b) return void(f = max(f, t[u].v1));
	PushDown(u);
	if(x <= mid) Query0(t[u].l, x, f, a, mid);
	else f = max(f, t[t[u].l].v1), Query0(t[u].r, x, f, mid + 1, b);
}
inline void Query1(int u, int x, LL &f, int a = 1, int b = s)
{
	if(!u) return ;
	if(a == b) return void(f = max(f, t[u].v0 + xx[x]));
	PushDown(u);
	if(x <= mid) f = max(f, t[t[u].r].v0 + xx[x]), Query1(t[u].l, x, f, a, mid);
	else Query1(t[u].r, x, f, mid + 1, b);
}
inline void Merge(int &u, int v, LL &f, int a = 1, int b = s)
{
	if(!u || !v) return void(u |= v);
	if(a == b)
	{
		f = max(f, max(t[u].v0 + t[v].v1, t[v].v0 + t[u].v1));
		t[u].v0 = max(t[u].v0, t[v].v0);
		t[u].v1 = max(t[u].v1, t[v].v1);
		return ;
	}
	PushDown(u), PushDown(v);
	f = max(f, max(t[t[u].r].v0 + t[t[v].l].v1, t[t[v].r].v0 + t[t[u].l].v1));
	t[u].v0 = max(t[u].v0, t[v].v0);
	t[u].v1 = max(t[u].v1, t[v].v1);
	Merge(t[u].l, t[v].l, f, a, mid);
	Merge(t[u].r, t[v].r, f, mid + 1, b);
}

inline void Add(int a, int b)
{
	ne[ ++ idx] = la[a];
	la[a] = idx;
	en[idx] = b;
}

inline LL DP(int u, int fa)
{
	LL f = 0, f0, s = 0;
	for(int i = la[u]; i; i = ne[i])
	{
		int v = en[i];
		if(v != fa)
		{
			f0 = DP(v, u);
			s += f0;
			Change(rt[v], -f0);
			Merge(rt[u], rt[v], f);
		}
	}
	Query0(rt[u], a[u], f);
	Query1(rt[u], a[u], f);
	f += s;
	Insert(rt[u], a[u], 0);
	Change(rt[u], s);
	// printf("*%d %d %d %lld\n", u, a[u], xx[a[u]], f);
	return f;
}

int main()
{
	Read(n);
	for(int i = 1; i <= n; i ++ ) Read(a[i]), xx[i] = a[i];
	sort(xx + 1, xx + n + 1);
	s = unique(xx + 1, xx + n + 1) - xx - 1;
	for(int i = 1; i <= n; i ++ ) a[i] = lower_bound(xx + 1, xx + s + 1, a[i]) - xx;
	for(int i = 1; i < n; i ++ )
	{
		int a, b;
		Read(a), Read(b);
		Add(a, b), Add(b, a);
	}
	t[0].v0 = t[0].v1 = -1e18;
	printf("%lld\n", DP(1, 0));
	return 0;
}