题意：每个城堡有一定价值的财宝，可以选择攻打m个城市。但是攻打有些城市之前一定要先
攻打其他的城市。现在已知每个城堡中财宝的价值和城市间的依赖关系。求选择攻打m个城市
能获得的最大价值。
分析：
虽然题目没有明确指出。但是很明显这是一个存在依赖关系的背包问题，而且是依赖中有依赖（可能攻打
a必须先攻打b，而攻打b又要先攻打c）
我们把这种依赖关系用树表示，必须先攻打的是父亲，后攻打的是他的儿子。
dp[i][j]表示选择以i节点为根的子树中j个节点得到的最大财富值。
这样就有两种方案，分别对应了两个子问题：
1】选择以i的第x个儿子t为根的子树中的j-k个节点，然后选择以i为根的除x为根的子树外的其他子节点
（包括它自己）的k个节点。（注意这里出现了子树中的子树的概念，就是有j-k个节点是集中在子树的
子树中选）
2】直接在以i为根的树中（只涉及到i的下一层，也就是i的儿子）选j个节点。
我们已经知道dp[i][1]=val（输入的财宝价值），因为选1个一定会选自己。
依赖关系形成森林，进行树形dp前要把森林转化为树，所以
要加一个根节点：0。结果就是dp[0][m+1] （包括增加的根节点一共m+1个点）
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int mp[210][210],num[210],dp[210][210];
int vis[210],n,m;
int maxx(int x,int y)
{
return x>y?x:y;
}
void dfs(int r)
{
vis[r]=1;
for(int i=1;i<=num[r];i++)
{
int t=mp[r][i];
if(!vis[t])
dfs(t);
for(int j=m;j>=2;j--)
{
for(int k=1;k<j;k++)
{
if(dp[t][j-k]!=-1 && dp[r][k]!=-1)
dp[r][j]=maxx(dp[r][j],dp[t][j-k]+dp[r][k]);
}
}
}
}
int main()
{
int a,b;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==0 && m==0)
break;
memset(num,0,sizeof(num));
dp[0][1]=0;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&a,&b);
dp[i][1]=b;
mp[a][++num[a]]=i;
}
m++;
for(int i=0;i<=n;i++)
{
vis[i]=0;
dp[i][0]=0;
for(int j=2;j<=m;j++)
dp[i][j]=-1;
}
dfs(0);
printf("%d\n",dp[0][m]);
}
return 0;
}