#[160].树形背包

内存限制：512 MB 时间限制：600 ms

有 $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}$

一个整数，表示答案

选择 3, 4, 5 号结点

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

$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$）。

子任务组	分值	$N=$	$W\le$	特性	依赖的子任务
1	1	21	25	森林，全是树根
2	2	22	26	一棵树
3	3	23	27	菊花
4	4	24	28	森林	2
5	5	100	120	一棵树	1, 3, 4
6	10	200	250	森林，$v_i=1$	5
7	10	200	200	森林，$w_i=1$	5
8	10	200	250	森林	6, 7
9	15	400	500	森林	8
10	20	7500	8000	森林	9
11	10	50000	1200	森林	10
12	10	1000	60000	森林	10

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

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

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

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

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

160 树形背包