P12582 「KTSC 2019 R1」树

**请使用 C++17 或 C++20 提交本题** 你需要在程序开头加入如下代码： ```cpp #include long long findSum(int N, std::vectorC, std::vector Node1, std::vector Node2); ``` 题目译自 [2019년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사](https://www.ioikorea.kr/archives/ioitst/2019/) T1「[트리](https://assets.ioikorea.or.kr/ioitst/2019/1/tree/tree_statement.pdf)」

有一棵包含 $N$ 个节点的树 $T=(V, E)$。每个节点上写有一个整数（可以为负）。我们需要找到满足以下条件的两棵子图 $T_{a}=\left(V_{a}, E_{a}\right)$ 和 $T_{b}=\left(V_{b}, E_{b}\right)$： - $V_{a} \neq \varnothing, V_{b} \neq \varnothing$； - $T_{a}$ 和 $T_{b}$ 都是连通图； - $V_{a} \cap V_{b}=\varnothing$； - $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\leq i\leq N-1)$ 的节点上写的数为 $C_i$。编号为 $Node1_i$ 和 $Node2_i (0\leq i\leq N-2)$ 的节点由一条边连接。 这些函数必须按照上述描述工作。当然，你可以创建其他函数并在内部使用。提交的代码不得进行输入输出操作或访问其他文件。

示例评测程序将按照以下格式读取输入： - 第 $1$ 行：$N$ - 第 $2$ 行：$N$ 个整数 $C_{0}, C_{1}, \ldots, C_{N-1}$，表示每个节点的值。 - 接下来的 $N-1$ 行：两个整数 $a$ 和 $b$，表示编号为 $a$ 和 $b$ 的节点由边连接。 注意：每行最后一个数字后面不得有空格或其他字符，否则示例评测程序可能无法正确工作。

示例评测程序将输出 `findSum()` 函数的返回值。

对于所有输入数据，满足： - $-10^{9} \leq C_{i} \leq 10^{9}$ - $3 \leq N \leq 5\cdot 10^5$ 详细子任务附加限制及分值如下表所示。 | Subtask | 分值 | 约束 | | :----------: | :----------: | :----------: | | $1$ | $7$ | $N \le 20$ | | $2$ | $19$ | $N \le 5000$ | | $3$ | $74$ | 无附加限制 |