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;

#define REP(i, a) for(int64 i = 0; i < (a);i++)
#define FOR(i, a, b) for(int64 i = (a); i < (b); i++)
#define INF (int64)1e9
#define INF_LL (int64)1e18
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int32_t;
using int64 = int64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

template<typename A, typename B> inline void chmin(A &a, B b) { if (a > b) a = b;}
template<typename A, typename B> inline void chmax(A &a, B b) { if (a < b) a = b;}

template<typename Data, typename T>
struct ReRooting {
  struct Node {
    int to, rev;
    Data data;
  };

  using F1 = function<T(T, T)>;
  using F2 = function<T(T, Data)>;

  vector<vector<Node>> g;
  vector<vector<T>> ldp, rdp;
  vector<int> lptr, rptr;
  const F1 f1;
  const F2 f2;
  const T ident;

  ReRooting(int n, const F1 &f1, const F2 &f2, const T &ident) : g(n), ldp(n), rdp(n), lptr(n), rptr(n), f1(f1), f2(f2), ident(ident) {}

  void add_edge(int u, int v, const Data& d) {
    g[u].emplace_back((Node) {v, (int)g[v].size(), d});
    g[v].emplace_back((Node) {u, (int)g[u].size()-1, d});
  }

  void add_edge_bi(int u, int v, const Data& d, const Data& e) {
    g[u].emplace_back((Node) {v, (int)g[v].size(), d});
    g[v].emplace_back((Node) {u, (int)g[u].size()-1, e});
  }

  T dfs(int idx, int par) {
    while (lptr[idx] != par && lptr[idx] < g[idx].size()) {
      auto &e = g[idx][lptr[idx]];
      ldp[idx][lptr[idx] + 1] = f1(ldp[idx][lptr[idx]], f2(dfs(e.to, e.rev), e.data));
      ++lptr[idx];
    }
    while (rptr[idx] != par && rptr[idx] >= 0) {
      auto &e = g[idx][rptr[idx]];
      rdp[idx][rptr[idx]] = f1(rdp[idx][rptr[idx] + 1], f2(dfs(e.to, e.rev), e.data));
      --rptr[idx];
    }
    if (par < 0) return rdp[idx][0];
    int64 a, b, c;
    tie(a, b, c) = f1(ldp[idx][par], rdp[idx][par+1]);
//    cout << idx << " " << g[idx][par].to << ": " << a << " " << b << " " << c << endl;
    return f1(ldp[idx][par], rdp[idx][par + 1]);
  }

  vector<T> solve() {
    for (int i = 0; i < g.size(); i++) {
      ldp[i].assign(g[i].size() +1, ident);
      rdp[i].assign(g[i].size() + 1, ident);
      lptr[i] = 0;
      rptr[i] = (int) g[i].size() - 1;
    }
    vector<T> ret(g.size());
    for (int i = 0; i < g.size(); i++) {
      ret[i] = dfs(i, -1);
    }
    return ret;
  }
};

int64 N;
vector<int64> p;
vector<int64> G[112345];

int main(void) {
  using T = tuple<int64, int64, int64>;
  auto f1 = [](const T& l, const T& r) {
    int64 a1, b1, c1, a2, b2, c2;
    tie(a1, b1, c1) = l;
    tie(a2, b2, c2) = r;
//    assert(max(a1+b2, a2+b1) - a1-a2 != max(c1, c2));
    return T(a1+a2, max(a1+b2, a2+b1), max(c1, c2));
  };

  auto f2 = [](const T& l, const int64& p) {
    int64 a, b, c;
    tie(a, b, c) = l;
    int64 na = max({a+p-2, (int64)0}), nb = max({b+p-1, (int64)0});
    return T(na, nb, nb-na);
  };
  cin >> N;
  ReRooting<int64, T> reroot(N, f1, f2, T(0, 0, 0));

  p.resize(N);
  REP(i, N) {
    cin >> p[i];
  }
  REP(i, N-1) {
    int64 s, t;
    cin >> s >> t; s--; t--;
    reroot.add_edge_bi(s, t, p[t], p[s]);
  }

  auto res = reroot.solve();
  int64 ret = -INF_LL;
  REP(i, res.size()) {
    int64 a, b, c;
    tie(a, b, c) = res[i];
    chmax(ret, b + p[i]);
    chmax(ret, a + p[i]);
  }
  cout << ret << endl;
}