問題
给出一个每个顶点都有数值的有向树。 你可以以成本 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
注意,父母的数值必须真正大于子代的数值,不能相等。