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"

#define REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

class RootedNode{
public:
	int index,rank,use{0},rest{-1};
};

auto pair_comp = [](const pair<int,int>& l,const pair<int,int>& r){return l.first==r.first ? l.second<r.second : l.first<r.first;};

class ConnectNodeInfo{
	vector<vector<pair<ll,ll>>> graph;
public:
	ConnectNodeInfo(int node_num){
		graph.resize(node_num);
	}
	void AddNonDirectionalConnection(ll u,ll v){
		graph[u].emplace_back(v,0);
		graph[v].emplace_back(u,0);
	}
	vector<pair<ll,ll>>& operator[](ll index){
		return graph[index];
	}
	size_t size(){return graph.size();}
};

class Point{
public:
	int first,second,fake;
};

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);

	int N=in();
	auto P=vecin(N);
	ConnectNodeInfo connect(N);
	REP(i,N-1){
		int u=in()-1,v=in()-1;
		connect.AddNonDirectionalConnection(u,v);
	}

	vector<vector<Point>> point(N);

	auto comp = [](RootedNode& l,RootedNode& r){return l.rest>r.rest;};
	priority_queue<RootedNode,vector<RootedNode>,decltype(comp)> Q(comp);
	vector<RootedNode> tree(N);
	REP(i,N){
		tree[i].index = i;
		tree[i].rank = connect[i].size();
		if(tree[i].rank==1) Q.push(tree[i]);
	}

	set<pair<int,int>,decltype(pair_comp)> visit(pair_comp);

	int max_score = P[0];
	while(!Q.empty()){
		auto node = Q.top();
		Q.pop();
		int connect_index=-1;
		for(int i=0,ei=connect[node.index].size();i<ei;i++){
			//if(!connect[node.index][i].second){
			int l = node.index,r = connect[node.index][i].first;
			if(l>r) swap(l,r);
			if(visit.find(make_pair(l,r))==visit.end()){
				connect_index = connect[node.index][i].first;
				visit.emplace(l,r);
				break;
			}
		}
		if(connect_index==-1){
			int score=0;
			point[node.index].erase(remove_if(ALL(point[node.index]),[](Point& v){return (v.first)<=0;}),point[node.index].end());
			sort(ALL(point[node.index]),[](Point& l,Point& r){return l.second==r.second ? l.first>r.first :l.second>r.second;});
			for(int i=0,ei=point[node.index].size();i<2;i++){
				for(int j=2;j<ei;j++){
					if(point[node.index][i].first-1<point[node.index][j].second){
						swap(point[node.index][i],point[node.index][j]);
					}
				}
			}
			for(int i=0,ei=point[node.index].size();i<ei;i++){
				if(i>1) score += max(point[node.index][i].first-1-point[node.index][i].second+point[node.index][i].fake,0);
				else{
					score += point[node.index][i].first-1;
				}
			}
			score += P[node.index];
			max_score = max(max_score,score);
		}
		else{
			Point prev_point={0,0,0};
			point[node.index].erase(remove_if(ALL(point[node.index]),[](Point& v){return (v.first)<=0;}),point[node.index].end());
			//sort(ALL(point[node.index]),[](Point& l,Point& r){return l.second==r.second ? l.first<r.first : l.second<r.second;});
			sort(ALL(point[node.index]),[](Point& l,Point& r){return l.second-l.fake<r.second-r.fake;});
			for(int i=0,ei=point[node.index].size();i<ei-1;i++){
				prev_point.first += max(point[node.index][i].first-1-point[node.index][i].second+point[node.index][i].fake,0);
				point[node.index][i].second = 0;
			}
			if(!point[node.index].empty()){
				prev_point.first += point[node.index].back().first-1;
				if(prev_point.first){
					prev_point.second = point[node.index].back().second;
					prev_point.fake = point[node.index].back().fake;
				}
			}
			prev_point.first += P[node.index];
			max_score = max(max_score,prev_point.first);
			prev_point.second++;
			if(prev_point.first<=prev_point.second){
				prev_point.fake = max(prev_point.fake,prev_point.second+1-prev_point.first);
			}
			point[connect_index].push_back(prev_point);
			tree[connect_index].rest = max(tree[connect_index].rest,prev_point.second);
			tree[connect_index].use++;
			if(tree[connect_index].rank-tree[connect_index].use==1){
				Q.push(tree[connect_index]);
			}
		}
	}

	out(max_score);
	return 0;
}