树上问题
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小蓝遇到了这样的一个问题, n  个点,  n-1  条边,形式上它是一颗树,你需要从 n 个点中选取 3 个,并且 3 个点的所取得的代价之和最大。一个点的代价等于以从这个点出发,每个点最多走一次,所能到达的所有结点的取值之和。形式上,可以把该节点当作根节点,每次你可以访问当前节点的其中一个儿子,一直到叶子节点停止,你所访问的所有节点的权值和为你能获得的代价,事实上你需要通过某种方法使该点代价最大。同时你所选取的 3 个点必须是直接相连的,形式上,存在一个点直接连接另外两个点。 

输入描述:

第一行一个整数 n ,代表有 n 个点 。
第二行 n 个整数,第 i 个整数代表点 i 的权值 a_i 。
接下来 n-1 行,每行两个整数代表 u_i , v_i 两点相连 。
 

输出描述:

一行一个整数,代表结果。
示例1

输入

复制 
3
1 2 3
1 2
2 3

输出

复制 
17

说明

节点 1,2,3 所能达到的代价是 6,5,6 ,只能选取节点 1,2,3 所以答案为 17 。
示例2

输入

复制 
6
1 2 3 4 5 6
1 2
1 3
1 4
1 5
1 6

输出

复制 
31

说明

节点 1,2,3,4,5,6 所能达到的代价是 7,9,10,11,12,12 ,可以选择联通的三个节点 1,5,6 所以答案为 31 。