题目描述

有 $N$ 个物品，编号分别为 $1\ldots N$。物品 $i$ 的重量为 $w_i$，价值为 $v_i$。

给出每个物品依赖于哪个物品。我们用 $d_i = j$ $(i>j>0)$ 表示：如果要选取物品 $i$，就必须先选取物品 $j$。另外，我们用 $d_i = 0$ $(i>0)$ 表示：该物品不依赖于任何物品。保证每个物品最多只依赖一个物品。保证依赖关系合理，不会出现环。

背包最多能装载的重量为 $W$，请问背包中最多能装入多大价值的物品。

输入格式

$N\ \ W$
$d_{\large 1\dots N}$
$w_{\large 1\dots N}$
$v_{\large 1\dots N}$

输出格式

一个整数，表示答案

7 0
3 4 5 3 0 7 0
1 2 2 1 1 2 2
1 1 2 3 1 1 2

0

7 4
3 4 5 3 0 7 0
1 2 2 1 1 2 2
1 1 2 3 1 1 2

6

10 6
0 1 1 1 2 3 4 5 6 7
1 1 2 2 3 1 2 2 3 1
0 1 1 1 1 1 1 1 1 1

3

13 3
0 1 1 1 3 3 0 0 8 9 10 8 10
1 1 1 1 1 1 1 1 1 1 1 1 1
2 16 32 512 2048 4096 4 1 8 64 1024 128 256

4130

13 25
0 1 1 1 3 3 0 0 8 9 10 8 10
5 6 4 3 7 5 4 7 3 6 5 6 6
0 2 1 2 3 3 3 0 1 2 4 3 2

10

数据范围与提示

$1\le N×W\le 6×10^7,$ $1\le N\le 5×10^4,$ $0\le W\le 6×10^4;$

$1\le w_i\le 200;$

$0\le v_i\le 5000$.

如果你感觉这里的二维数组很难定义，可以先开一个一维的 int 数组，假设名字为 pool；等到读入了 $N$, $W$ 后再这样声明

int (&dp)[n+1][w+1]=decltype(dp)(pool);

之后就可以写 dp[i][j] 了（其中 $i=0\ldots N,$ $j=0\ldots W$）。

子任务