给定一棵包含 $N$ 个节点的树 $T=(V, E)$。树中的每个节点都写有一个整数。请注意，这些整数也可能是负数。我们希望找到 $T$ 的两个子图 $T_a=(V_a, E_a)$ 和 $T_b=(V_b, E_b)$，满足以下条件：

• $V_a \neq \emptyset, V_b \neq \emptyset$
• $T_a$ 和 $T_b$ 均为连通图。
• $V_a \cap V_b = \emptyset$
• 此外，在原图 $E$ 中不存在连接 $V_a$ 中的节点与 $V_b$ 中的节点的边。
• 最后，使得 $V_a$ 中节点上的整数之和与 $V_b$ 中节点上的整数之和的总和最大。

考虑下图所示的例子。$T = (\{0, 1, 2, 3, 4, 5, 6\}, \{(0, 1), (0, 2), (2, 3), (2, 4), (4, 6), (5, 6)\})$。

节点上的数字是节点的编号，节点内的数字是该节点上的值。满足上述条件的 $T_a$ 和 $T_b$ 的选取方式有多种，但若取 $V_a = \{0, 2, 3\}$，$V_b = \{5, 6\}$，则两个图中的数值之和为 $\{3 + (-1) + 4\} + \{5 + 3\} = 14$，达到最大值。虽然存在其他选取方式，但无法得到大于 14 的值。

你需要实现以下函数：

long long findSum(int N, int C[], int Node1[], int Node2[]);

这是一个仅会被调用一次的函数。输入通过参数传递，该函数的返回值即为问题的答案。$N$ 表示节点的数量。节点编号从 $0$ 到 $N-1$。当变量 $i$ 的值在 $0$ 到 $N-1$ 之间时，编号为 $i$ 的节点上的数值为 $C[i]$。此外，当变量 $i$ 的值在 $0$ 到 $N-2$ 之间时，编号为 $Node1[i]$ 的节点与编号为 $Node2[i]$ 的节点之间有一条边相连。

实现细节

你需要提交一个名为 tree.cpp 的文件。该文件中必须实现上述函数。

long long findSum(int N, int C[], int Node1[], int Node2[]);

该函数应按上述说明运行。当然，你可以在内部创建并使用其他函数。提交的代码不得执行输入输出操作，也不得访问其他文件。

数据范围

• $-10^9 \leq C_i \leq 10^9$
• $3 \leq N \leq 500,000$

子任务

• 子任务 1 [7 分]：$N \leq 20$
• 子任务 2 [19 分]：$N \leq 5000$
• 子任务 3 [74 分]：无额外限制。

样例

输入样例 1

7
3 -5 -1 4 2 5 3
0 1
0 2
2 3
2 4
4 6
5 6

输出样例 1

14