P12710 [KOI 2021 Round 1] 两个团队

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。

某公司的组织架构可以用一棵有根树（rooted tree）来表示。树中的每个节点表示一名员工，边表示直属上下级关系。每位员工从 $1$ 到 $N$ 编号，其中编号 $1$ 的员工是公司的总裁，即树的根节点。每位员工都有一个整数形式的“能力值”，该能力值可能为负数。 下面是一棵示意组织树的例子，节点内的数字表示员工编号。  现在希望从中选择若干人担任“团队负责人”。每位团队负责人必须组成自己的团队，团队必须满足以下条件： 1. 团队成员必须是该负责人下属员工（不一定是直属下属）。例如，如果员工 $3$ 是负责人，那么员工 $8$ 或 $11$ 可以是团队成员，但员工 $1$ 或 $9$ 不可以。 2. 如果某员工被包含为团队成员，那么该员工的直属上司也必须被包含为团队成员（负责人除外）。例如，若员工 $3$ 是负责人，则团队为 $\{3, 6, 11\}$ 是合法的，但 $\{3, 8, 11\}$ 是不合法的，因为员工 $11$ 的上司 $6$ 没有被包含。 3. 团队的得分定义为团队负责人及所有成员的能力值总和，团队成员的选择必须使团队得分最大。（若得分最大的团队组成不唯一，可任选其一。）例如，在所有员工的能力值均为正的情况下，若员工 $3$ 被选为负责人，则其团队必须为 $\{3, 6, 7, 8, 11, 12\}$，其中任何一人缺席都不被允许。 4. 员工不能同时属于两个团队（包括不能作为另一个团队的负责人）。也就是说，若某员工 $A$ 是负责人，其下属 $B$ 由于第 3 条必须包含进 $A$ 的团队，则 $A$ 和 $B$ 都不能被选为负责人。 公司最终希望选出两名团队负责人，组成两个团队，使这两个团队的得分总和（即所有成员能力值之和的总和）最大。 请你编写一个程序，计算在满足所有约束条件的前提下，这两个团队得分之和的最大值。 输入保证一定存在合法的两个团队的构成方式。

第一行输入一个整数 $N$，表示员工人数。 接下来的 $N$ 行中，每行输入两个整数，分别表示第 $i$ 位员工的能力值和直属上司的编号，两数之间以空格分隔。其中员工 $1$ 没有上司，因此其上司编号为 $-1$。

输出一个整数，表示两个团队得分之和的最大值，占据一行。 （提示：输出结果可能非常大，请在 C/C++ 中使用 `long long` 类型，在 Java 中使用 `long` 类型。）

**约束条件** - $2 \leq N \leq 200\,000$ - 每名员工的能力值在 $-1\,000\,000\,000$ 到 $1\,000\,000\,000$ 之间 - 除员工 $1$ 外的每位员工 $i$ 的直属上司编号不超过 $i - 1$ - 输入保证一定可以构成符合要求的两个团队 **子任务** 1. （17 分）所有员工的能力值均为正数 2. （12 分）$N \leq 5\,000$，且员工 $i$ 的直属上司为 $i - 1$（员工 $1$ 除外） 3. （20 分）员工 $i$ 的直属上司为 $i - 1$（员工 $1$ 除外） 4. （16 分）$N \leq 400$ 5. （17 分）$N \leq 5\,000$ 6. （18 分）无附加约束条件