Problem: Bob is playing a game called "Dungeon 2" which is the sequel to the popular "Dungeon" released last year. The game is played on a map consisting of $N$ rooms and $N-1$ roads connecting them. The roads allow bidirectional traffic and the player can start his tour from any room and reach any other room by way of multiple of roads. A point is printed in each of the rooms.

Bob tries to accumulate the highest score by visiting the rooms by cleverly routing his character "Tora-Tora." He can add the point printed in a room to his score only when he reaches the room for the first time. He can also add the points on the starting and ending rooms of Tora-Tora’s journey. The score is reduced by one each time Tora-Tore passes a road. Tora-Tora can start from any room and end his journey in any room.

Given the map information, make a program to work out the maximum possible score Bob can gain.



Input

The input is given in the following format.


$N$
$p_1$
$p_2$
$...$
$p_N$
$s_1$ $t_1$
$s_2$ $t_2$
$...$
$s_{N-1}$ $t_{N-1}$


The first line provides the number of rooms $N$ ($1 \leq N \leq 100,000$). Each of the subsequent $N$ lines provides the point of the $i$-th room $p_i$ ($-100 \leq p_i \leq 100$) in integers. Each of the subsequent lines following these provides the information on the road directly connecting two rooms, where $s_i$ and $t_i$ ($1 \leq s_i < t_i \leq N$) represent the numbers of the two rooms connected by it. Not a single pair of rooms are connected by more than one road.

Output

Output the maximum possible score Bob can gain.

Examples

Input

7
6
1
-1
4
3
3
1
1 2
2 3
3 4
3 5
5 6
5 7


Output

10


Input

4
5
0
1
1
1 2
2 3
2 4


Output

5

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<ll,ll> P;
#define M 1000000007
#define F first
#define S second
#define PB push_back
#define INF 100000000000000000
#define MP make_pair
struct t{
	ll r,s1,s2;
	t(void){r=0,s1=0,s2=0;}
	void up(ll x){
		if(s1<x)swap(s1,x);
		s2=max(s2,x);
	}
	void mn(ll x){
		if(s1==x){
			s1=s2;
			s2=0;
		}
	}
};
ll n,cs[100005],ans;
vector<ll>g[100005];
map<ll,t>dp[100005];
t dfs(ll v,ll p,ll f){
	if(dp[v].count(p))return dp[v][p];
	t res;
	if(p==-1||f){
		for(int i=0;i<g[v].size();i++){
			ll u=g[v][i];
			if(u==p)continue;
			t x=dfs(u,v,f);
			x.r-=2;
			x.s1--;
			if(x.r>0){
				res.r+=x.r;
				res.up(-x.r+x.s1);
			}else res.up(x.s1);
		}
		res.r+=cs[v];
		res.s1+=res.r;
		res.s2+=res.r;
	}else{
		res=dfs(v,-1,0);
		t x=dfs(p,v,0);
		x.r-=2;
		x.s1--;
		if(x.r>0){
			res.r-=x.r;
			res.mn(res.r+x.s1);
			res.s1-=x.r;
		}else res.mn(res.r+x.s1);
	}
	return dp[v][p]=res;
}
int main(void){
	scanf("%lld",&n);
	ll ma=-INF;
	for(int i=0;i<n;i++){
		scanf("%lld",cs+i);
		ma=max(ma,cs[i]);
	}
	if(ma<=0){
		printf("%lld\n",ma);
		return 0;
	}
	for(int i=0;i<n-1;i++){
		ll a,b;
		scanf("%lld%lld",&a,&b);
		g[--a].PB(--b);
		g[b].PB(a);
	}
	dfs(0,-1,1);
	for(int i=0;i<n;i++)ans=max(ans,dfs(i,-1,0).s1);
	printf("%lld\n",ans);
}