No.3283 Labyrinth and Friends
タグ : / 解いたユーザー数 55
作問者 :
hirayuu_yc
/ テスター :
highlighter
Problem Statement
By unlocking the vertices of a rooted tree called the "Labyrinth Zone", the status of the Friends increases.
There is a rooted tree with $N$ vertices and $N-1$ edges, whose vertices are numbered $1,2,\dots,N$. The root is vertex $1$, and the parent of vertex $i$ $(2\leq i)$ is vertex $p_i$.
Initially, only vertex $1$ is unlocked, and the status of the Friends is $0$. The Captain can perform the following operation any number of times: "unlock a vertex that is not yet unlocked and whose parent vertex is already unlocked". The cost of unlocking vertex $i$ $(2\leq i)$ is $c_i$, and unlocking it increases the status of the Friends by $s_i$.
Find the minimum cost required to make the status of the Friends at least $X$. It is guaranteed that this is possible.
Constraints
- $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$
- All input values are integers.
Input
$N$ $X$ $p_2$ $p_3$ $\dots$ $p_N$ $c_2$ $s_2$ $c_3$ $s_3$ $\vdots$ $c_N$ $s_N$
Output
Output the answer.
Sample
Sample 1
Input
4 34 1 1 3 1 9 2 24 2 10
Output
4
It is optimal to unlock vertices $3,4$ in this order.
Sample 2
Input
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
Output
18804815148
This is the actual shape of the Labyrinth Zone. Typing the tree in by hand was tough...
Note that the answer may not fit in a 32-bit integer.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。