#2930. [GDKOI]海星

[GDKOI]海星

题目描述

小明想去海底抓海星, 海底是一个树状的结构,而海星就藏在里面。 给定一棵 nn 个点的树,分别标号为 1,2,3,...,n1,2,3, ..., n, 且对应的点权记为 pip_i。 定义海星为其中的花子图,不妨设其中心节点标号为 OO, 边缘节点标号为 a1,a2,...,ata_1, a_2, ..., a_t(其中边缘节点必 定直接与中心节点相连,同时花子图至少由一个中心节点和一个边缘节点构成)。

此时记海星的价值为 pOpai|p_O − \sum p_{a_i} |

小明想知道他最多能抓到价值总和为多少的海星。(可以同时抓很多只海星,但是任意两个海星之间点的 交集必须为空) 补充定义:

花图:直径小于等于三的联通图,其中度数最大的节点为中心节点,其余节点为边缘节点(可知任意的边缘节点度数为一)示例:最小的花图,是(G,V)=(1,2,(1,2)),仅由两个节点和联结它们的一条边构成花图: 直径小于等于三的联通图,其中度数最大的节点为中心节点,其余节点为边缘节点(可知任意的边缘节点度数为一)示例:最小的花图,是 (G,V)=({1,2},{(1,2)}),仅由两个节点和联结它们的一条边构成

输入格式

第一行,一个正整数 nn,表示树的大小;

22 行,nn 个整数,表示 pip_i

3n+13 ∼ n+1 行,每行 22 个整数 aa, bb,分别表示 aa 号节点与 bb 号节点之间有一条边。

输出格式

一行,一个整数,表示小明能抓到的最大海星的价值总和。

输入样例1

5
-2 -3 4 -5 1
1 2
1 3
2 4
2 5

输出样例1

10

输入样例2

10
-2 9 7 -11 0 9 -6 -10 -11 3
3 1
3 2
3 4
3 5
3 6
3 7
3 8
3 9
3 10

输出样例2

47

样例解释

一个合法的方案是,小明抓了两个海星,第一个海星的中心节点为 11,边缘节点为 33,价值为 66

第二个 海星的中心节点为 22,边缘节点为 55,价值为 44,此时得到最大总价值 1010

数据范围

(1)(1) 对于 10%10\% 的数据,保证数据形成一个花图

(2)(2) 对于 20%20\% 的数据,保证数据形成一条链。

(3)(3) 对于 20%20\% 的数据,保证数据相邻节点乘积恒负。

(4)(4) 对于 20%20\% 的数据,保证数据形成一颗以 11 为根节点的二叉树。

(5)(5) 对于 30%30\% 的数据,无特殊限制。

对于所有数据 1a,bn105,109pi1081 ≤ a, b ≤ n ≤ 10^5,−10^9 ≤ p_i ≤ 10^8

下发样例中编号为 i,i+5i, i+5 的数据对应序号为 ii 的限制条件. i1,2,3,4,5i ∈ {1,2,3,4,5}