[AdditionalFile160.zip](file://AdditionalFile160.zip?type=additional_file)

题目描述

有 $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_{ 1\dots N}$
$w_{ 1\dots N}$
$v_{ 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

选择 3, 4, 5 号结点

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

选择 1, 2, 3, 6 号或 1, 2, 4, 7 号结点

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 \times W \le 6 \times 10^7$, $1 \le N \le 5 \times 10^4$, $0 \le W \le 6 \times 10^4$;
• $1 \le w_i \le 200$;
• $0 \le v_i \le 5000$.

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

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

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