题目描述

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

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

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

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

输入格式

第一行，一个正整数 $n$，表示树的大小；

第 $2$ 行，$n$ 个整数，表示 $p_i$；

第 $3 ∼ n+1$ 行，每行 $2$ 个整数 $a$, $b$，分别表示 $a$ 号节点与 $b$ 号节点之间有一条边。

输出格式

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

输入样例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

样例解释

一个合法的方案是，小明抓了两个海星，第一个海星的中心节点为 $1$，边缘节点为 $3$，价值为 $6$；

第二个 海星的中心节点为 $2$，边缘节点为 $5$，价值为 $4$，此时得到最大总价值 $10$。

数据范围

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

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

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

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

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

对于所有数据 $1 ≤ a, b ≤ n ≤ 10^5,−10^9 ≤ p_i ≤ 10^8$。

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