题目背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

某公司的组织架构可以用一棵有根树（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 类型。）

4
3 -1
-2 1
2 2
-1 1

5

提示

约束条件

• $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 分）无附加约束条件