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;
using LL = long long;

const LL INF = 123456789012345;

int N;
LL p[123456];
vector<int>G[123456];
int par[123456];
vector<int>child[123456];
void dfs(int x,int las){
	par[x] = las;
	for(int nx : G[x]){
		if(nx != las){
			dfs(nx,x);
			child[x].push_back(nx);
		}
	}
}

bool visit[123456][2];
LL memo[123456][2];
vector<LL>diff[123456];
LL dp(int x,int f){
	if(visit[x][f])return memo[x][f];
	visit[x][f]=true;
	LL res=p[x];
	//dp(x,0) dp(x,1) 共通
	for(int ch:child[x]){
		res+=max(dp(ch,0)-2,0LL);
		if(f){
			//dp(x,1)のみ
			diff[x].push_back(max(dp(ch,1)-1,0LL) - max(dp(ch,0)-2,0LL));
		}
	}
	if(f){
		sort(diff[x].rbegin(),diff[x].rend());
		if(!diff[x].empty()){
			res += diff[x][0];
		}
	}
	return memo[x][f] = res;
}

bool visit2[123456][2];
LL memo2[123456][2];
LL ep(int x,int f){
	if(visit2[x][f])return memo2[x][f];
	visit2[x][f] = true;
	//dp(親,f) without x を取得
	if(x == 0){
		return memo2[x][f] = 0;
	}
	LL rawsum = dp(par[x],0);
	LL ep0=ep(par[x],0);
	LL ep1=ep(par[x],1);
	LL pdif = max(ep1-1,0LL)-max(ep0-2,0LL);
	//diff[par[x]].push_back(max(ep1,0)-max(ep0,0));
	//sort(diff[par[x]].rbegin(),diff[par[x]].rend());
	rawsum += max(ep0 - 2,0LL);
	if(f){
		if(pdif >= diff[par[x]][0]){
			//親へのdifが一番の時、それを足す。この時、これが削除されることはあり得ない
			rawsum += pdif;
			rawsum -= max(dp(x,0) - 2,0LL);
		}else if(max(dp(x,1)-1,0LL)-max(dp(x,0)-2,0LL) == diff[par[x]][0]){
			//自分が不幸にして一番になってしまった場合、難しいことをする
			if(diff[par[x]].size()==1){
				//自分しかいないので、max(ep(par[x],1)-2,0LL) + p[par[x]]が答え
				rawsum = max(ep1-1,0LL) + p[par[x]];
			}else{
				rawsum -= max(dp(x,0)-2,0LL);
				rawsum += diff[par[x]][1];
			}
		}else{
			//一番ではないときは難しくないのでうれしい
			rawsum -= max(dp(x,0)-2,0LL);
			rawsum += diff[par[x]][0];
		}
	}else{
		rawsum -= max(dp(x,0)-2,0LL);
	}
	return memo2[x][f] = rawsum;
}

int main(){
	cin>>N;
	for(int i=0;i<N;++i){
		cin>>p[i];
	}
	for(int i=0;i<N-1;++i){
		int u,v;
		cin>>u>>v;
		--u;--v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(0,-1);
	for(int i=0;i<N;++i){
		for(int f=0;f<2;++f){
			dp(i,f);
		}
	}
	vector<LL>zero,diffs;
	for(int i=0;i<N;++i){
		LL ep0=ep(i,0);
		LL ep1=ep(i,1);
		zero.push_back(max(ep0-2,0LL));
		diffs.push_back(max(ep1-1,0LL)-max(ep0-2,0LL));
	}
	LL ans = -INF;
	for(int i=0;i<N;++i){
		//diff[i].push_back(diffs[i]);
		//sort(diff[i].rbegin(),diff[i].rend());
		LL rawsum = dp(i,0);
		rawsum += zero[i];
		LL DPi0 = rawsum;//この時のrawsumがDP(i,0)
		LL chmax = (diff[i].size() > 0) ? diff[i][0] : 0;
		LL almax = max(chmax,diffs[i]);
		rawsum += almax;
		LL DPi1 = rawsum;//この時のrawsumがDP(i,1)
		ans = max(ans,DPi0);
		ans = max(ans,DPi1);
		//cerr <<dp(i,0)<<" " <<dp(i,1) <<" "<<ep(i,0) << " " << ep(i,1) << endl;
		
	}
	cout << ans << endl;
	return 0;
}