← 返回题目列表

Codeforces · 533/B

B. 工作组

中文机器翻译题面 查看原题

一家大型软件公司有 n 名员工,编号从 1 到 n。董事的编号为 1。除董事外,公司的每位员工都只有一名直接上级。当然,导演没有上级。

如果 b 是 a 的直接主管,或者 a 的直接主管是 b 的下属,我们将称 a 为另一个 b 的下属。特别是,领导的下属都是公司的其他员工。

为了解决实现重要目标,我们需要组建一个工作组。每个人都有一定的效率,用正整数ai表示,其中i是人的编号。工作组的效率定义为该工作组中所有人员的总效率。

大型软件公司的员工痴迷于现代的工作流程组织方式。如今结对编程正处于流行的顶峰,因此工作组的组建应满足以下条件。每个进入工作组的人都应该能够将他也在工作组中的所有下属分为两对。换句话说,对于工作组的每个成员来说,其在工作组内的下属数量应该是偶数。

您的任务是确定在观察给定条件时形成的工作组的最大可能效率。包括公司董事在内的任何人都可以进入工作组。

输入

第一行包含整数 n (1 ≤ n ≤ 2·105) — 大软件公司的员工数量。

接下来是 n 行,描述公司员工。第i行包含两个整数pi,ai(1≤ai≤105)——第i个员工的顶头上司和第i个员工的效率的人数。对于导演 p1 = - 1,对于所有其他人,满足条件 1 ≤ pi < i。

输出

打印单个整数 — 工作组的最大可能效率。

示例

输入 #1

7
-1 3
1 2
1 1
1 4
4 5
4 3
5 2

输出 #1

17

注意

在样本测试中,最有效的方法是由 1、2、4、5、6 号员工组成一个工作组。