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 <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#pragma warning (disable: 4996)

long long N, P[1 << 17], A[1 << 17], B[1 << 17], dp[1 << 17], ans[1 << 17][3], dp2[1 << 17][4];
vector<int> X[1 << 17], Y[1 << 17];
bool used[1 << 17];

void init() {
	for (int i = 0; i < 100; i++) {
		P[i] = 0; A[i] = 0; B[i] = 0; dp[i] = 0;
		X[i].clear(); Y[i].clear(); used[i] = false;
		for (int j = 0; j < 3; j++) ans[i][j] = 0;
		for (int j = 0; j < 4; j++) dp2[i][j] = 0;
	}
}

void dfs(int pos) {
	used[pos] = true; dp[pos] = P[pos];
	for (int i = 0; i < X[pos].size(); i++) {
		int to = X[pos][i];
		if (used[to] == true) continue;

		Y[pos].push_back(to);
		dfs(to);
		if (dp[to] >= 2) dp[pos] += dp[to] - 2;
	}
}

void dfs2(int pos) {
	for (int i = 0; i < Y[pos].size(); i++) dfs2(Y[pos][i]);

	ans[pos][0] = dp[pos];
	ans[pos][1] = dp[pos];
	ans[pos][2] = dp[pos];

	// 基本的な計算
	long long sum = 0;
	for (int i = 0; i < Y[pos].size(); i++) {
		sum += max(0LL, dp[Y[pos][i]] - 2LL);
	}
	for (int i = 0; i < Y[pos].size(); i++) {
		ans[pos][0] = max(ans[pos][0], P[pos] + ans[Y[pos][i]][0] + sum - max(0LL, dp[Y[pos][i]] - 2LL) - 1LL);
		ans[pos][1] = max(ans[pos][1], P[pos] + ans[Y[pos][i]][1] + sum - max(0LL, dp[Y[pos][i]] - 2LL) - 1LL);
		ans[pos][2] = max(ans[pos][2], P[pos] + ans[Y[pos][i]][1] + sum - max(0LL, dp[Y[pos][i]] - 2LL) - 1LL);
		ans[pos][2] = max(ans[pos][2], P[pos] + ans[Y[pos][i]][0] + sum - max(0LL, dp[Y[pos][i]] - 2LL) - 1LL);
		ans[pos][2] = max(ans[pos][2], P[pos] + ans[Y[pos][i]][2] + sum - max(0LL, dp[Y[pos][i]] - 2LL) - 2LL);
	}

	// スタートとゴールが合成される場合の計算
	for (int i = 0; i <= Y[pos].size(); i++) {
		for (int j = 0; j <= 3; j++) dp2[i][j] = -(1LL << 60);
	}
	dp2[0][0] = 0;
	for (int i = 0; i < Y[pos].size(); i++) {
		for (int j = 0; j < 4; j++) {
			if (dp2[i][j] == -(1LL << 60)) continue;
			dp2[i + 1][j] = max(dp2[i + 1][j], dp2[i][j] + max(0LL, dp[Y[pos][i]] - 2LL));
			if ((j & 1) == 0) dp2[i + 1][j + 1] = max(dp2[i + 1][j + 1], dp2[i][j] + ans[Y[pos][i]][0] - 1LL);
			if ((j & 2) == 0) dp2[i + 1][j + 2] = max(dp2[i + 1][j + 2], dp2[i][j] + ans[Y[pos][i]][1] - 1LL);
		}
	}
	ans[pos][2] = max(ans[pos][2], P[pos] + dp2[Y[pos].size()][3]);
}

void Input() {
	scanf("%lld", &N);
	for (int i = 1; i <= N; i++) scanf("%lld", &P[i]);
	for (int i = 1; i <= N - 1; i++) scanf("%lld%lld", &A[i], &B[i]);
}

long long solve_Output() {
	for (int i = 1; i <= N - 1; i++) {
		X[A[i]].push_back(B[i]);
		X[B[i]].push_back(A[i]);
	}
	dfs(1);
	dfs2(1);
	long long ret = -(1LL << 60);
	for (int i = 1; i <= N; i++) ret = max(ret, ans[i][2]);
	return ret;
}

long long dfs2(int pos, int dep, int s) {
	long long pointget = 0; if ((s / (1 << pos)) % 2 == 0) pointget = P[pos];
	if (dep == 13 || s == (2 << N) - 2) return pointget;

	long long r = pointget;
	for (int i = 0; i < X[pos].size(); i++) {
		r = max(r, dfs2(X[pos][i], dep + 1, (s | (1 << pos))) + pointget - 1LL);
	}
	return r;
}

long long solve_Jury() {
	long long maxn = -(1LL << 60);
	for (int i = 1; i <= N; i++) maxn = max(maxn, dfs2(i, 0, 0));
	return maxn;
}

void random_generate() {
	N = 11;
	for (int i = 1; i <= N; i++) P[i] = rand() % 9 - 4;
	for (int i = 1; i <= N - 1; i++) {
		B[i] = i + 1; A[i] = rand() % i + 1;
	}
}

int Debug = 1;

int main() {
	if (Debug == 1) {
		Input();
		long long e1 = solve_Output();
		cout << e1 << endl;
	}
	else {
		for (int t = 1; t <= 1000000; t++) {
			init();
			random_generate();
			long long e1 = solve_Output();
			long long e2 = solve_Jury();
			if (t % 1000 == 0) cout << t << " " << e1 << " " << e2 << endl;

			if (e1 != e2) {
				cout << "Wrong Answer on Test #" << t << endl;
				cout << "Jury = " << e2 << ", Output = " << e1 << endl;
				cout << endl;
				cout << N << endl;
				for (int i = 1; i <= N; i++) cout << P[i] << " "; cout << endl;
				for (int i = 1; i <= N - 1; i++) cout << A[i] << " " << B[i] << endl;
				cout << endl;
			}
		}
	}
	return 0;
}