【题意】：在一个地图上，有N座城堡，每座城堡都有一定的宝物，在每次游戏中允许攻克M个城堡并获得里面的宝物。但由于地理位置原因，有些城堡不能直接攻克，要攻克这些城堡必须先攻克其他某一个特定的城堡。求获得尽量多的宝物应该攻克哪M个城堡。
【题解】：经典的树dp+分组背包。
由于本题不是一个真正意义上的树，而是一个树林，可增加一个新结点0连向各个树根，转换成一棵树。
设dp[i][j]表示以i为根的子树，取j个结点（包括i本身）所得的最大宝藏。
转移方程：
dp[i][j] = max(dp[i1][j1] + dp[i2][j2] + dp[i3][j3] + …… + dp[in][jn]) + val[i];
其中i1,i2……in为i的儿子 且 j1 + j2 + j3 + …… + jn = j - 1;
对于i的每个儿子，都有很多不同价值、不同代价的子树，我们可以将他们泛化成物品，这样就把问题转换成背包问题。
我们把i的每个儿子的子树所形成的不同物品归为一组，显然对于每一组物品，我们要么取一个，要么不取，既不能取两个或两个以上。[认真思考]
这样就成为经典的分组背包问题，具体可以参考背包九讲。
由于我们新加了根，所以 ans = dp[0][m+1];
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "vector"
5 using namespace std;
6 #define pb push_back
7 #define maxn 205
8 #define maxm 205
9 int n, m;
10 vector<int> g[maxn];
11 int dp[maxn][maxm], val[maxn];
12
13 void init() {
14 for(int i = 0; i < maxn; i++) g[i].clear();
15 memset(dp, 0, sizeof(dp));
16 }
17
18 void dfs(int u) {
19 int size = g[u].size();
20 for(int i = 0; i < size; i++) {
21 int v = g[u][i];
22 dfs(v);
23 for(int j = m; j >= 0; j--)
24 for(int k = 0; k <= j; k++)
25 dp[u][j] = max(dp[u][j], dp[u][j-k] + dp[v][k]);
26 }
27 for(int j = m + 1; j >= 1; j--) dp[u][j] = dp[u][j-1] + val[u];
28 // cout << dp[u][0] << endl;
29 }
30
31 int main() {
32 while(~scanf("%d%d", &n, &m)) {
33 if(!n && !m) break;
34 init();
35 for(int i = 1; i <= n; i++) {
36 int u;
37 scanf("%d%d", &u, &val[i]);
38 g[u].pb(i);
39 }
40 dfs(0);
41 printf("%d\n", dp[0][m+1]);
42 }
43 return 0;
44 }
45