3932: 树形背包
内存限制：512 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
有 $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 4
3 4 5 3 0 7 0
1 2 2 1 1 2 2
1 1 2 3 1 1 2样例输出 复制
6提示
输入样例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
输出样例2
3
输入样例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
输出样例3
4130
输入样例4
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
输出样例4
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$ 后再这样声明 ```cpp int (&dp)[n+1][w+1]=decltype(pool)(dp); ``` > 之后就可以写 `dp[i][j]` 了（其中 $i=0\ldots N,$ $j=0\ldots W$）。