U661996 疯狂的背包问题(14) - 有依赖的背包问题

动态规划问题中的有依赖背包问题模板题，物品之间存在依赖关系。

有 $N$ 个物品和一个容量为 $V$ 的背包。 物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点（若有）。 每个物品只有一件，每件物品的体积为 $v_i$，价值为 $w_i$。 求解将哪些物品装入背包，可使物品总体积不超过背包容量，且价值总和最大。输出最大价值。

第一行有两个整数 $N$ 和 $V$，用空格隔开，分别表示物品个数和背包容积。 接下来有 $N$ 行，每行有三个整数 $v_i$、$w_i$、$p_i$，用空格隔开，分别表示第 $i$ 个物品的体积、价值和依赖关系。 * 如果 $p_i = -1$，表示该物品是根节点，没有依赖； * 如果 $p_i > 0$，表示该物品依赖于第 $p_i$ 个物品，即如果要选择物品 $i$，则必须同时选择物品 $p_i$。

输出一个整数，表示最大价值。

**样例 1 解释**： 物品1是根节点，物品2和3依赖于物品1，物品4和5依赖于物品2。 最优方案：选择物品1、物品2、物品4，总体积 = 3 + 2 + 5 = 10，总价值 = 5 + 3 + 8 = 16。 **数据范围** * $1 \leq N \leq 100$ * $1 \leq V \leq 100$ * $1 \leq v_i, w_i \leq 100$ * $-1 \leq p_i \leq N$，且 $p_i \neq i$