【題意】：在一個地圖上，有N座城堡，每座城堡都有一定的寶物，在每次游戲中允許攻克M個城堡并獲得里面的寶物。但由于地理位置原因，有些城堡不能直接攻克，要攻克這些城堡必須先攻克其他某一個特定的城堡。求獲得盡量多的寶物應該攻克哪M個城堡。

【題解】：經(jīng)典的樹dp+分組背包。
               由于本題不是一個真正意義上的樹，而是一個樹林，可增加一個新結(jié)點0連向各個樹根，轉(zhuǎn)換成一棵樹。
               設dp[i][j]表示以i為根的子樹，取j個結(jié)點（包括i本身）所得的最大寶藏。
               轉(zhuǎn)移方程：
                     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的每個兒子，都有很多不同價值、不同代價的子樹，我們可以將他們泛化成物品，這樣就把問題轉(zhuǎn)換成背包問題。
               我們把i的每個兒子的子樹所形成的不同物品歸為一組，顯然對于每一組物品，我們要么取一個，要么不取，既不能取兩個或兩個以上。[認真思考]
               這樣就成為經(jīng)典的分組背包問題，具體可以參考背包九講。
               由于我們新加了根，所以 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