题目链接

传送门

Description

现在我们的手头有N个软件,对于一个软件i,它要占用Wi的磁盘空间,它的价值为Vi。我们希望从中选择一些软件安装到一台磁盘容量为M计算机上,使得这些软件的价值尽可能大(即Vi的和最大)。

但是现在有个问题:软件之间存在依赖关系,即软件i只有在安装了软件j(包括软件j的直接或间接依赖)的情况下才能正确工作(软件i依赖软件j)。幸运的是,一个软件最多依赖另外一个软件。如果一个软件不能正常工作,那么它能够发挥的作用为0。

我们现在知道了软件之间的依赖关系:软件i依赖软件Di。现在请你设计出一种方案,安装价值尽量大的软件。一个软件只能被安装一次,如果一个软件没有依赖则Di=0,这时只要这个软件安装了,它就能正常工作。

Input

第1行:N, M (0<=N<=100, 0<=M<=500)
第2行:W1, W2, ... Wi, ..., Wn (0<=Wi<=M )
第3行:V1, V2, ..., Vi, ..., Vn (0<=Vi<=1000 )
第4行:D1, D2, ..., Di, ..., Dn (0<=Di<=N, Di≠i )

Output

一个整数,代表最大价值。

Sample Input

3 10

5 5 6

2 3 4

0 1 1

Sample Output

5

题解

树上背包
注意到大概是n个点b条边 大概是个基环树
先tarjan缩点 对于一个强连通分量要么选要么不选
现在是个森林 加上一个超级父节点就是一棵树
这个时候我们做树上背包
表示第i个强连通分量的子树花费j的体积产生的最大收益(选i点就有收益 不选就是0)
dp转移是这样的

其中to是子节点
然后需要判断这个点能不能选
能选的话

其中wei表示强连通分量的重量 val表示价值
不能直接赋值0 因为取不上

代码