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<cassert>
using namespace std;
#define rep(i, n) for ( int i = 0; i < (int)n; i++ )
static const int N_MAX = 100000;
static const int NINF = -1000000000;
int N, P[N_MAX], ans;
int dp[N_MAX][3];
vector<int> T[N_MAX];
bool V[N_MAX];

void dfs(int u){
  V[u] = true;
  vector<int> C;
  rep (i, T[u].size()){
    int v = T[u][i];
    if ( !V[v] ) {
      C.push_back(v);
      dfs(v);
    }
  }

  if ( C.size() == 0 ){
    rep(i, 3) dp[u][i] = P[u];
  } else if ( C.size() == 1 ){
    int v = C[0];
    dp[u][0] = max(dp[v][0] - 1 + P[u], P[u]);
    dp[u][1] = max(dp[v][1] - 2 + P[u], P[u]);
    dp[u][2] = max(dp[v][2] - 2 + P[u], P[u]);
  } else {
    int a1, a2, c1;
    a1 = a2 = c1 = C[0];
    rep (i, C.size()){
      int v = C[i];
      if ( dp[a1][0] - 1 - max(dp[a1][1] -  2, 0) <= dp[v][0] - 1 - max(dp[v][1] - 2, 0) ) a1 = v;
      if ( dp[c1][2] - 2 - max(dp[c1][1] -  2, 0) <= dp[v][2] - 2 - max(dp[v][1] - 2, 0) ) c1 = v;
    }
    rep(i, C.size()) if ( C[i] != a1 ) { a2 = C[i]; break; }
    rep(i, C.size()){
      int v = C[i];
      if ( v == a1 ) continue;
      if ( dp[a2][0] - 1 - max(dp[a2][1] -  2, 0) <= dp[v][0] - 1 - max(dp[v][1]  - 2, 0) ) a2 = v;
    }
    int sumA1 = 0;
    int sumB1 = 0;
    int sumC1 = 0;
    int sumC2 = 0;
    for ( int i = 0; i < C.size(); i++ ){
      int v = C[i];
      sumA1 += (v == a1) ? (dp[v][0] - 1) : max(dp[v][1] - 2, 0);
      sumB1 += max(dp[v][1] - 2, 0);
      sumC1 += (v == c1) ? (dp[v][2] - 2) : max(dp[v][1] - 2, 0);
      sumC2 += (v == a1 || v == a2) ? (dp[v][0] - 1) : max(dp[v][1] - 2, 0);
    }
    int sumA = sumA1;
    int sumC = max(sumC1, sumC2);
    int sumB = sumB1;
    dp[u][0] = max(P[u], sumA + P[u]);
    dp[u][1] = max(P[u], sumB + P[u]);
    dp[u][2] = max(P[u], sumC + P[u]);
  }
  rep(i, 3) ans = max(ans, dp[u][i]);
}

int solve(int s){
  rep(i, N) rep(j, 3) dp[i][j] = NINF;
  rep(i, N) V[i] = false;
  ans = NINF;
  dfs(s);
  return ans;
}

int main(){
  cin >> N;
  for ( int i = 0; i < N; i++ ) cin >> P[i];
  for ( int i = 0; i < N - 1; i++ ) {
    int s, t; cin >> s >> t;
    s--; t--;
    T[s].push_back(t);
    T[t].push_back(s);
  }

  int a = solve(0);
  cout << a << endl;

  return 0;
}