1 /*  2 根据先后关系，可以建立一棵树  3 dp[i][j]表示第i个节点选j个的最大值  4 dp[i][j]=max(sigma(dp[c[i][ki]]))  5 sigma(dp[c[i][ki]])表示从i的儿子节点中一共选取j个点的最大值  6 */  7 /*#include <iostream>  8 #include <cstdio>  9 #include <cstring> 10 #include <vector> 11 using namespace std; 12  13 const int maxn=205; 14 int dp[maxn][maxn]; 15 int val[maxn],n,m,num[maxn]; 16 vector<int> f[maxn]; 17 inline int max(int a,int b){return a>b?a:b;} 18  19 void dfs1(int u,int id,int s1,int s2) 20 { 21     if(s1>m+1 || s1>num[u]) 22         return ; 23     if(id==f[u].size()) 24     { 25         dp[u][s1]=max(dp[u][s1],s2); 26         return ; 27     } 28     for(int i=0;i<=num[f[u][id]];i++) 29         dfs1(u,id+1,s1+i,s2+dp[f[u][id]][i]); 30     return ; 31 } 32  33 void dfs(int u) 34 { 35     if(f[u].size()==0) 36     { 37         dp[u][1]=val[u];num[u]=1; 38         return ; 39     } 40     int temp=0; 41     for(int i=0;i<f[u].size();i++) 42     { 43         int v=f[u][i]; 44         dfs(v); 45         temp+=num[v]; 46     } 47     num[u]=temp; 48     dp[u][1]=val[u]; 49     dfs1(u,0,1,dp[u][1]); 50     return ; 51 } 52 int main() 53 { 54     int i,a; 55     while(~scanf("%d%d",&n,&m),n+m) 56     { 57         for(i=0;i<=n;i++) f[i].clear(); 58         val[0]=0; 59         for(i=1;i<=n;i++) 60         { 61             scanf("%d%d",&a,val+i); 62             f[a].push_back(i); 63         } 64         m++; 65         memset(dp,0,sizeof(dp)); 66         memset(num,0,sizeof(num)); 67         dfs(0); 68         printf("%d\n",dp[0][m]); 69     } 70     return 0; 71 } 72 */ 73 /* 74 上面代码没剪枝，傻逼了忘了可以用0-1背包优化。 75 */ 76 #include <iostream> 77 #include <cstdio> 78 #include <cstring> 79 #include <vector> 80 using namespace std; 81  82 const int maxn=205; 83 int dp[maxn][maxn]; 84 int val[maxn],n,m; 85 vector<int> f[maxn]; 86 inline int max(int a,int b){return a>b?a:b;} 87  88 void dfs(int u,int sum) 89 { 90     dp[u][1]=val[u]; 91     if(m<=1) return; 92     for(int i=0;i<f[u].size();i++) 93     { 94         int v=f[u][i]; 95         dfs(v,sum-1); 96         for(int j=sum;j>=2;j--) 97         { 98             for(int k=1;k<j;k++) 99                 dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]);100         }101     }102     return ;103 }104 int main()105 {106     int i,a;107     while(~scanf("%d%d",&n,&m),n+m)108     {109         for(i=0;i<=n;i++) f[i].clear();110         val[0]=0;111         for(i=1;i<=n;i++)112         {113             scanf("%d%d",&a,val+i);114             f[a].push_back(i);115         }116         m++;117         memset(dp,0,sizeof(dp));118         dfs(0,m);119         printf("%d\n",dp[0][m]);120     }121     return 0;122 }