1 //狀態(tài)轉(zhuǎn)移方程：    dp[i][j]=max(dp[i][j],dp[i][j-k]+dp[son[i]][k])    
 2 //                    以第i個(gè)城市為起點(diǎn)，攻占j個(gè)城市的最大收益
 3 
 4 #include <iostream>
 5 #include <cstring>
 6 using namespace std;
 7 #define MaxSize 205
 8 
 9 int dp[MaxSize][MaxSize];
10 int value[MaxSize];
11 int mapmap[MaxSize][MaxSize];
12 bool vis[MaxSize];
13 int n,m;
14 
15 inline int max(int a,int b){
16     return a>b?a:b;
17 }
18 
19 void dfs(int root){
20     int i,j,k,u;
21     dp[root][1]=value[root];
22     for(i=1;i<=mapmap[root][0];i++){
23         u=mapmap[root][i];//root之后可以選擇攻占的城市
24         dfs(u);
25         for(j=m+1;j>0;j--){
26             for(k=1;k+j<=m+1;k++){
27                 dp[root][j+k]=max(dp[root][j+k],dp[root][j]+dp[u][k]);
28             }
29         }
30     }
31 }
32 
33 int main(){
34     //freopen("in.txt","r",stdin);
35     int i;
36     while (scanf("%d%d",&n,&m),(n||m)){
37         for(i=0;i<=n;i++)
38             mapmap[i][0]=0;
39         value[0]=0;
40         for(i=1;i<=n;i++){
41             int a;
42             scanf("%d %d",&a,&value[i]);
43             mapmap[a][0]++;
44             mapmap[a][mapmap[a][0]]=i;
45         }
46         memset(dp,0,sizeof(dp));
47         //問(wèn)題的關(guān)鍵在于將0作為第零個(gè)城堡，價(jià)值為零，這樣就可以實(shí)現(xiàn)大一統(tǒng)！
48         dfs(0);
49         printf("%d\n",dp[0][m+1]);//加入了第零個(gè)城堡，則m+1
50     }
51     return 0;
52 }