問題一覧 > 通常問題

No.3283 Labyrinth and Friends

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 47
作問者 : hirayuu_yc / テスター : highlighter
ProblemId : 12270 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-09-25 21:03:56

問題文

「迷宮ゾーン」と呼ばれる根付き木の頂点を解放していくことで、フレンズのステータスが上がります。

頂点に $1,2,\dots,N$ と番号が付けられた $N$ 頂点 $N-1$ 辺の根付き木があります。根は頂点 $1$ で、頂点 $i$ $(2\leq i)$ の親は頂点 $p_i$ です。

はじめ、頂点 $1$ のみが解放されていて、フレンズのステータスは $0$ です。隊長は、「すでに親の頂点が解放されている頂点を解放する」ことを任意の回数行うことができます。頂点 $i$ $(2\leq i)$ を解放するのにかかるコストは $c_i$ で、解放することでフレンズのステータスが $s_i$ 増加します。

フレンズのステータスを $X$ 以上にするために必要なコストの最小値を求めてください。ただし、そのようなことが可能であることは保証されます。

制約

  • $1\leq N\leq 2000$
  • $1\leq X\leq 2000$
  • $1\leq p_i\lt i$
  • $1\leq c_i\leq 10^9$
  • $0\leq s_i$
  • $1\leq X\leq \sum_{i=2}^{N}s_i\leq 2000$
  • 入力はすべて整数

入力

$N$ $X$
$p_2$ $p_3$ $\dots$ $p_N$
$c_2$ $s_2$
$c_3$ $s_3$
$\vdots$
$c_N$ $s_N$

出力

答えを出力せよ。

サンプル

サンプル1
入力
4 34
1 1 3
1 9
2 24
2 10
出力
4

頂点 $3,4$ の順に解放するとよいです。

サンプル2
入力
92 500
1 2 2 2 5 5 5 8 5 10 5 12 13 12 15 12 17 18 19 19 21 22 17 24 25 25 27 28 17 30 31 31 33 34 35 36 37 30 39 39 41 42 43 44 45 30 47 48 49 50 51 52 53 54 55 55 57 58 59 59 61 48 63 64 65 47 67 68 69 70 71 72 73 74 74 76 77 78 78 80 67 82 83 84 47 86 87 88 86 90 91
631379418 18
864081790 4
130231439 5
964472850 7
456057010 4
347665106 19
163317081 19
177992555 12
364308678 10
962146530 7
739020081 8
116911710 0
709538376 19
747858399 6
382393013 0
251270448 17
751767115 12
250371205 3
505605770 8
725486248 6
910634675 9
626034182 19
502217696 16
967526692 14
498031593 5
33922299 4
637259783 12
622998184 9
763237708 14
137208366 6
632193884 1
735374011 2
643795092 12
208815313 12
826449214 9
769687287 14
465924224 17
955500992 12
678084788 11
970828044 2
80936220 9
688748843 2
271932063 5
347582992 13
327975281 13
806976042 7
838172339 4
156795463 0
2316145 10
535308734 2
587219865 14
9723876 13
476035052 16
83061778 10
68483687 1
368546853 12
105334853 11
858777793 13
257497982 15
67164727 6
230837118 7
724891091 14
777820422 13
632046331 5
794754576 12
827365398 11
578883518 11
522611399 7
78615116 20
568842382 19
913764455 14
906782645 3
85544517 3
821863778 11
371051101 16
394955834 5
746058863 1
571993592 3
346333022 2
618587673 19
15879647 10
26536775 3
632199410 20
392338405 11
128957825 12
662722322 3
289755335 11
501065500 5
958933403 13
88315547 2
514607068 8
出力
18804815148

実際の迷宮ゾーンの形です。木を手打ちするの大変だった…

答えが32bit整数の範囲に収まらない場合があることに注意してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。