#P12582. 「KTSC 2019 R1」树

「KTSC 2019 R1」树

题目背景

请使用 C++17 或 C++20 提交本题

你需要在程序开头加入如下代码:

#include <vector>
long long findSum(int N, std::vector<int>C, std::vector<int> Node1, std::vector<int> Node2);

题目译自 2019년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사 T1「트리

题目描述

有一棵包含 NN 个节点的树 T=(V,E)T=(V, E)。每个节点上写有一个整数(可以为负)。我们需要找到满足以下条件的两棵子图 Ta=(Va,Ea)T_{a}=\left(V_{a}, E_{a}\right)Tb=(Vb,Eb)T_{b}=\left(V_{b}, E_{b}\right)

  • Va,VbV_{a} \neq \varnothing, V_{b} \neq \varnothing
  • TaT_{a}TbT_{b} 都是连通图;
  • VaVb=V_{a} \cap V_{b}=\varnothing
  • EE 中没有连接 VaV_{a} 中节点和 VbV_{b} 中节点的边;
  • 最后,我们希望 VaV_{a} 中所有节点的整数之和与 VbV_{b} 中所有节点的整数之和的总和尽可能大。

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

节点上的数字表示节点编号,节点内的数字表示该节点上的值。可以有多种方法找到符合条件的 TaT_{a}TbT_{b},但选择 Va={0,2,3}V_{a}=\{0,2,3\}Vb={5,6}V_{b}=\{5,6\},两个子图中的整数和为 {3+(1)+4}+{5+3}=14\{3+(-1)+4\}+\{5+3\}=14,这是最大的值。虽然有其他方法,但无法得到比 1414 更大的值。

你需要实现以下函数:

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

该函数将会被调用一次,传入输入参数并返回问题的答案。NN 表示节点数,节点编号从 00N1N-1。编号为 i(0iN1)i (0\leq i\leq N-1) 的节点上写的数为 CiC_i。编号为 Node1iNode1_iNode2i(0iN2)Node2_i (0\leq i\leq N-2) 的节点由一条边连接。

这些函数必须按照上述描述工作。当然,你可以创建其他函数并在内部使用。提交的代码不得进行输入输出操作或访问其他文件。

输入格式

示例评测程序将按照以下格式读取输入:

  • 11 行:NN
  • 22 行:NN 个整数 C0,C1,,CN1C_{0}, C_{1}, \ldots, C_{N-1},表示每个节点的值。
  • 接下来的 N1N-1 行:两个整数 aabb,表示编号为 aabb 的节点由边连接。

注意:每行最后一个数字后面不得有空格或其他字符,否则示例评测程序可能无法正确工作。

输出格式

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

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

提示

对于所有输入数据,满足:

  • 109Ci109-10^{9} \leq C_{i} \leq 10^{9}
  • 3N51053 \leq N \leq 5\cdot 10^5

详细子任务附加限制及分值如下表所示。

Subtask 分值 约束
11 77 N20N \le 20
22 1919 N5000N \le 5000
33 7474 无附加限制