← 返回题目列表

AtCoder · utpc2012_12

L. 上所树

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

問題

给出一个每个顶点都有数值的有向树。 你可以以成本 1 对某个顶点的数值进行 1 的修改。 也就是说,增加或减少某个顶点的数值 1 需要成本 1。 修改后的数值没有大小等限制。

你想要将给定的树变为“升高树”。升高树是指每个顶点的数值都大于它所有子节点的数值。编写程序,在输入树时,求出将其变为升高树所需的最小成本。


图 1:输入的树的例子

图 2:将图 1 的树数值修改为升高树的例子

入力

N C_1
P_2 C_2
...
P_N C_N

输入的 1 行是树的顶点数 N 和根节点所持的数值 C_1 被给出。 树有 N 个顶点,每个顶点有编号到 1 减去 N 。树的顶点 1 。

输入的 2 从行 N 行提供了关于各顶点的信息。 i 行包含顶点 字母写在 i 的父顶点编号 P_i 以及顶点 i 上写的数字 C_i 。

出力

将最小总成本输出为一行。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq P_i < i
  • -10^9 \leq C_i \leq 10^9

部分点

本问题的判定中,为50分的测试用例设置了分组。包含在该组中的测试用例输入额外满足以下条件。

  • N \leq 50
  • -50 \leq C_i \leq 50

入力例 1

8 6
1 1
2 1
2 3
1 9
5 6
6 6
6 2

输入示例 1 的输出示例

8

此输入对应上图。输入对应图1,例如如果像图2那样更改数值,可以以成本8将树变为升序树。


入力例 2

4 5
1 5
2 5
3 5

输入示例 2 的输出示例

4

注意,父母的数值必须真正大于子代的数值,不能相等。