東京大学プログラミングコンテスト2012

L - じょうしょうツリー


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題

各頂点が数値を持つ有向ツリーが与えられる. あなたは,コスト 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 行に出力せよ.

制約

部分点

この問題の判定には,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

親の数値は子の数値よりも真に大きくなければならず,等しくてはいけないことに注意せよ.


Submit提出する