実行時間制限: 2 sec / メモリ制限: 256 MB
問題
各頂点が数値を持つ有向ツリーが与えられる. あなたは,コスト 1 にて,ある頂点の数値を 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 行に出力せよ.
制約
- 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
親の数値は子の数値よりも真に大きくなければならず,等しくてはいけないことに注意せよ.