#2107. Knapsack Problem on Tree

Knapsack Problem on Tree

Description

There're NN items numbered from 1N1\ldots N, each item ii with a weight wiw_i and a value viv_i. The knapsack's capacity is WW.

Some items could be selected only after a specific item have been put into the knapsack, or in other words, some items depend on others.

  • di=jd_i = j (i>j>0)(i>j>0) means item ii depends on item jj, you cannot choose item ii until you put item jj into the knapsack.
  • di=0d_i = 0 (i>0)(i>0) means item ii does not depends on any other items.

It's guaranteed that each item depends on no more than one item. All the dependency relationships are vaild, no loop.

Maximize the sum of the values of the items in the knapsack so that the sum of the weights is no more than the knapsack's capacity.

Input

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

Output

A single integer, represents your answer.

Sample 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

Choose item 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

Choose item 1, 2, 3, 6, or chooose item 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

Limits And Hints

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.

Subtask id pts N=N= WW\le Additional Constraints Dependencies
1 ​1 21 25 Bare-root Forest
2 ​2 22 26 A Single Tree
3 ​3 23 27 Flower
4 ​4 24 28 A Forest 2
5 ​5 100 120 A Single Tree 1, 3, 4
6 ​10 200 250 Forest,vi=1v_i=1 5
7 10 200 Forest,wi=1w_i=1
8 ​10 250 ​Forest 6, 7
9 15 400 500 8
10 ​20 7500 8000 Forest 9
11 10 50000 1200 10
12 ​10 1000 60000