题目描述
小蓝遇到了这样的一个问题, nnn 个点, n−1n-1n−1 条边,形式上它是一颗树,你需要从 nnn 个点中选取 333 个,并且 333 个点的所取得的代价之和最大。一个点的代价等于以从这个点出发,每个点最多走一次,所能到达的所有结点的取值之和。形式上,可以把该节点当作根节点,每次你可以访问当前节点的其中一个儿子,一直到叶子节点停止,你所访问的所有节点的权值和为你能获得的代价,事实上你需要通过某种方法使该点代价最大。同时你所选取的 333 个点必须是直接相连的,形式上,存在一个点直接连接另外两个点。
输入
第一行一个整数 nnn ,代表有 nnn 个点 (3≤n≤105)(3 \le n\le 10^5)(3≤n≤105)。
第二行 nnn 个整数,第 iii 个整数代表点 iii 的权值 aia_iai (1≤ai≤109)(1 \le a_i \le 10^9)(1≤ai≤109)。
接下来 n−1n-1n−1 行,每行两个整数代表 ui,viu_i , v_iui,vi 两点相连 (1≤vi,ui≤n)( 1\le v_i , u_i \le n)(1≤vi,ui≤n)。
输出
一行一个整数,代表结果。
样例输入 Copy
3
1 2 3
1 2
2 3
样例输出 Copy
17
提示
节点 1,2,31,2,31,2,3 所能达到的代价是 6,5,66,5,66,5,6 ,只能选取节点 1,2,31,2,31,2,3 所以答案为 171717 。