{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n section pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n\t\t\t\n\t\t\t\u003ch3\u003e問題\u003c/h3\u003e\r\n\r\n\u003cp\u003e\r\n各頂点が数値を持つ有向ツリーが与えられる.\r\nあなたは,コスト 1 にて,ある頂点の数値を 1 変更することができる.\r\n即ち,ある頂点の数値を 1 増やすか1 減らすためにコストが 1 かかる.\r\n変更後の数値に大きさなどの制限はない.\r\n\u003c/p\u003e\r\n\r\n\u003cp\u003e\r\nあなたは,与えられたツリーを「じょうしょうツリー」にしたい.じょうしょうツリーとは,各頂点の持つ数値が,その全ての子の数値よりも大きいツリーのことである.ツリーが入力されたとき,そのツリーをじょうしょうツリーにするために必要な最小のコストを求めるプログラムを作成せよ.\r\n\u003c/p\u003e\r\n\r\n\u003ccenter\u003e\r\n\u003cimg src\u003d\"CDN_BASE_URL/6d67487315d733bcc5adb0d955559e54?v\u003d1715905735\"\u003e\u003cbr\u003e\r\n\u003ci\u003e図 1: 入力されるツリーの例\u003c/i\u003e\r\n\u003c/center\u003e\r\n\r\n\u003ccenter\u003e\r\n\u003cimg src\u003d\"CDN_BASE_URL/0711d3518395922a8709a30e5d63013b?v\u003d1715905735\"\u003e\u003cbr\u003e\r\n\u003ci\u003e図 2: 図 1 の木の数値を変更してじょうしょうツリーにした例\u003c/i\u003e\r\n\u003c/center\u003e\r\n\r\n\u003chr\u003e\r\n\r\n\u003ch3\u003e入力\u003c/h3\u003e\r\n\r\n\u003cpre\u003e\r\n\u003cvar\u003e\\(N\\)\u003c/var\u003e \u003cvar\u003e\\(C_1\\)\u003c/var\u003e\r\n\u003cvar\u003e\\(P_2\\)\u003c/var\u003e \u003cvar\u003e\\(C_2\\)\u003c/var\u003e\r\n\u003cvar\u003e\\(...\\)\u003c/var\u003e\r\n\u003cvar\u003e\\(P_N\\)\u003c/var\u003e \u003cvar\u003e\\(C_N\\)\u003c/var\u003e\r\n\u003c/pre\u003e\r\n\r\n\u003cp\u003e\r\n入力の \u003cvar\u003e\\(1\\)\u003c/var\u003e 行目には,ツリーの頂点数 \u003cvar\u003e\\(N\\)\u003c/var\u003e と根の頂点が持つ数値 \u003cvar\u003e\\(C_1\\)\u003c/var\u003e が与えられる.\r\nツリーは \u003cvar\u003e\\(N\\)\u003c/var\u003e 個の頂点を持ち,頂点には \u003cvar\u003e\\(1\\)\u003c/var\u003e から \u003cvar\u003e\\(N\\)\u003c/var\u003e までの番号が付いている.ツリーは頂点 \u003cvar\u003e\\(1\\)\u003c/var\u003e である.\r\n\u003c/p\u003e\r\n\r\n\u003cp\u003e\r\n入力の \u003cvar\u003e\\(2\\)\u003c/var\u003e 行目から \u003cvar\u003e\\(N\\)\u003c/var\u003e 行目には,各頂点に関する情報が与えられる.\r\n\u003cvar\u003e\\(i\\)\u003c/var\u003e 行目には,頂点 \u003cvar\u003e\\(i\\)\u003c/var\u003e の親の頂点の番号 \u003cvar\u003e\\(P_i\\)\u003c/var\u003e と,頂点 \u003cvar\u003e\\(i\\)\u003c/var\u003e に書かれた数字 \u003cvar\u003e\\(C_i\\)\u003c/var\u003e が与えられる.\r\n\u003c/p\u003e\r\n\r\n\u003ch3\u003e出力\u003c/h3\u003e\r\n\r\n\u003cp\u003e\r\n最小の合計コストを 1 行に出力せよ.\r\n\u003c/p\u003e\r\n\r\n\u003ch3\u003e制約\u003c/h3\u003e\r\n\r\n\u003cul\u003e\r\n\u003cli\u003e \u003cvar\u003e\\(1 \\leq N \\leq 10^5\\)\u003c/var\u003e\u003c/li\u003e\r\n\r\n\u003cli\u003e \u003cvar\u003e\\(1 \\leq P_i \u0026lt; i\\)\u003c/var\u003e\u003c/li\u003e\r\n\r\n\u003cli\u003e \u003cvar\u003e\\(-10^9 \\leq C_i \\leq 10^9\\)\u003c/var\u003e\u003c/li\u003e\r\n\r\n\u003c/ul\u003e\r\n\r\n\u003ch3\u003e部分点\u003c/h3\u003e\r\n\r\n\u003cp\u003e\r\nこの問題の判定には,50点分のテストケースのグループが設定されている. このグループに含まれるテストケースの入力は追加で以下の条件を満たす.\r\n\u003c/p\u003e\r\n\r\n\u003cul\u003e\r\n\u003cli\u003e \u003cvar\u003e\\(N \\leq 50\\)\u003c/var\u003e\u003c/li\u003e\r\n\r\n\u003cli\u003e \u003cvar\u003e\\(-50 \\leq C_i \\leq 50\\)\u003c/var\u003e\u003c/li\u003e\r\n\r\n\u003c/ul\u003e\r\n\r\n\u003chr\u003e\r\n\r\n\u003ch3\u003e入力例 1\u003c/h3\u003e\r\n\r\n\u003cpre\u003e\r\n8 6\r\n1 1\r\n2 1\r\n2 3\r\n1 9\r\n5 6\r\n6 6\r\n6 2\r\n\u003c/pre\u003e\r\n\r\n\u003ch3\u003e入力例 1 に対する出力例\u003c/h3\u003e\r\n\r\n\u003cpre\u003e\r\n8\r\n\u003c/pre\u003e\r\n\r\n\u003cp\u003e\r\nこの入力は上図に対応している.入力は図 1 に相当し,例えば図 2 のように数値を変更すればコスト 8 にてツリーをじょうしょうツリーにできる.\r\n\u003c/p\u003e\r\n\r\n\u003chr\u003e\r\n\r\n\u003ch3\u003e入力例 2\u003c/h3\u003e\r\n\r\n\u003cpre\u003e\r\n4 5\r\n1 5\r\n2 5\r\n3 5\r\n\u003c/pre\u003e\r\n\r\n\u003ch3\u003e入力例 2 に対する出力例\u003c/h3\u003e\r\n\r\n\u003cpre\u003e\r\n4\r\n\u003c/pre\u003e\r\n\r\n\u003cp\u003e\r\n親の数値は子の数値よりも真に大きくなければならず,等しくてはいけないことに注意せよ.\r\n\u003c/p\u003e\n\t\t"}}]}