#2107. Knapsack Problem on Tree

Knapsack Problem on Tree

题目描述

NN 个物品,编号分别为 1N1\ldots N。物品 ii 的重量为 wiw_i,价值为 viv_i

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

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

输入格式

N  WN\ \ W
d1Nd_{\large 1\dots N}
w1Nw_{\large 1\dots N}
v1Nv_{\large 1\dots N}

输出格式

一个整数,表示答案

样例 0

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

数据范围与提示

1N×W6×107,1\le N×W\le 6×10^7, 1N5×104,1\le N\le 5×10^4, 0W6×104;0\le W\le 6×10^4;

1wi200;1\le w_i\le 200;

0vi50000\le v_i\le 5000.

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

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

之后就可以写 dp[i][j] 了(其中 i=0N,i=0\ldots N, j=0Wj=0\ldots W)。

子任务

子任务组 分值 N=N= WW\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 森林,vi=1v_i=1 5
7 10 200 森林,wi=1w_i=1
8 ​10 250 ​森林 6, 7
9 15 400 500 8
10 ​20 7500 8000 森林 9
11 10 50000 1200 10
12 ​10 1000 60000