洛谷P2515[HAOI2010]软件安装
2521+
作者：crxis 发布：2017-06-06 分类：树形DP
题目大意：安装软件，每个软件都有价值，都需要占用磁盘空间，有些软件要跟其他软件一起安装才会产生价值，怎么安装才有最大价值？
题目描述
现在我们的手头有N个软件，对于一个软件i，它要占用Wi的磁盘空间，它的价值为Vi。我们希望从中选择一些软件安装到一台磁盘容量为M计算机上，使得这些软件的价值尽可能大（即Vi的和最大）。
但是现在有个问题：软件之间存在依赖关系，即软件i只有在安装了软件j（包括软件j的直接或间接依赖）的情况下才能正确工作（软件i依赖软件j)。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够发挥的作用为0。
我们现在知道了软件之间的依赖关系：软件i依赖软件Di。现在请你设计出一种方案，安装价值尽量大的软件。一个软件只能被安装一次，如果一个软件没有依赖则Di=0，这时只要这个软件安装了，它就能正常工作。
输入输出格式
输入格式：
第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 ）
输出格式：
一个整数，代表最大价值
输入输出样例
输入样例#1：
3 10 5 5 6 2 3 4 0 1 1
输出样例#1：
5
解题思路
把互相依赖的软件缩点成一个软件，然后用树形DP处理，注意要从子结点更新到父节点：每个结点在空间m下有不同的价值，这些不同的空间价值分别看成一个物品，要么选要么不选，更新到父亲结点；这样一层一层往上更新，汇集于根节点0。
程序实现
