CF633F.The Chocolate Spree

Alice and Bob have a tree (undirected acyclic connected graph). There are a__i chocolates waiting to be picked up in the i-th vertex of the tree. First, they choose two different vertices as their starting positions (Alice chooses first) and take all the chocolates contained in them.

Then, they alternate their moves, selecting one vertex at a time and collecting all chocolates from this node. To make things more interesting, they decided that one can select a vertex only if he/she selected a vertex adjacent to that one at his/her previous turn and this vertex has not been already chosen by any of them during other move.

If at any moment one of them is not able to select the node that satisfy all the rules, he/she will skip his turns and let the other person pick chocolates as long as he/she can. This goes on until both of them cannot pick chocolates any further.

Due to their greed for chocolates, they want to collect as many chocolates as possible. However, as they are friends they only care about the total number of chocolates they obtain together. What is the maximum total number of chocolates they may pick?

爱丽丝和鲍勃有一棵树（无向、无环、连通图）。树的第 $i$ 个顶点上有 $a_i$ 颗巧克力等待被采摘。首先，他们选择两个不同的顶点作为各自的起始位置（爱丽丝先选），并取走这两个顶点上所有的巧克力。

随后，他们轮流行动，每次选择一个顶点，并取走该顶点上的所有巧克力。为了增加趣味性，他们约定：一名玩家仅可在其上一轮所选顶点与当前欲选顶点相邻，且该顶点尚未被任何一方在之前的操作中选过时，才可选择该顶点。

若在某时刻，某位玩家无法选出满足上述所有规则的顶点，则他/她将跳过本轮行动，由另一位玩家继续采摘，直至其也无法继续采摘为止。如此反复，直到双方均无法再采摘巧克力为止。

由于他们对巧克力十分贪心，因此希望尽可能多地采摘巧克力。然而，作为朋友，他们只关心两人共同采摘到的巧克力总数。那么，他们最多能采摘多少颗巧克力？

The first line of the input contains the single integer n (2 ≤ n ≤ 100 000) — the number of vertices in the tree.

The second line contains n integers a__i (1 ≤ a__i ≤ 109), i-th of these numbers stands for the number of chocolates stored at the node i.

Then follow n - 1 lines that describe the tree. Each of them contains two integers u__i and v__i (1 ≤ u__i, v__i ≤ n) — indices of vertices connected by the i-th edge.

输入的第一行包含一个整数 $n$（$2 \leq n \leq 100\,000$）——树中顶点的数量。

第二行包含 $n$ 个整数 $a_i$（$1 \leq a_i \leq 10^9$），其中第 $i$ 个数表示节点 $i$ 上存储的巧克力数量。

接下来是 $n-1$ 行，用于描述该树。每行包含两个整数 $u_i$ 和 $v_i$（$1 \leq u_i,\,v_i \leq n$）——表示第 $i$ 条边所连接的两个顶点的编号。

Print the number of chocolates Alice and Bob can collect together if they behave optimally.

如果爱丽丝和鲍勃都采取最优策略，输出他们两人共同收集的巧克力总数。

In the first sample, Alice may start at the vertex 9 and Bob at vertex 8. Alice will select vertex 1 and Bob has no options now. Alice selects the vertex 7 and they both stop.

In the second sample, both of them will pick either of the nodes alternately.

在第一个样例中，Alice 可以从顶点 9 开始，Bob 从顶点 8 开始。Alice 将选择顶点 1，此时 Bob 已无可行选择。接着 Alice 选择顶点 7，双方均停止操作。

在第二个样例中，他们将轮流选择任一节点。