练习 5：树上背包问题

题目描述：

给定一棵以 1 为根的有根树，每个结点 i 有一个体积 v[i] 和价值 w[i]。现在有一个容量为 m 的背包，要选择一些结点放入背包，要求：

1. 如果选择了结点 u，则必须选择 u 的所有祖先
2. 在满足条件 1 的前提下，使得总价值最大

输入格式：

• 第一行：两个正整数 n, m（2 ≤ n ≤ 100，1 ≤ m ≤ 1000）
• 第二行：n-1 个正整数 f_2, f_3, ..., f_n，其中 f_i 表示结点 i 的父结点编号
• 接下来 n 行：每行两个正整数 v[i], w[i]（1 ≤ v[i] ≤ m，1 ≤ w[i] ≤ 1000）

输出格式：

• 一行，一个整数，表示最大总价值

样例输入：

5 10
1 1 2 2
2 5
3 8
1 3
2 4
1 2

样例输出：

18

提示：

• 树形背包 DP
• dp[u][j] 表示在 u 的子树中，使用容量 j 能获得的最大价值
• 转移：先强制选 u（消耗 v[u]），然后对每个子结点做背包合并
• 注意：必须选 u 才能选其子结点