给定n，m表示n个城堡，我们可以选择攻占m个城堡。要使得价值最大
接下来n行 a b, 第i行的a b，表示攻占第i个城堡的价值为b，但需要先攻占第a个城堡
如果有多个a=0的点，那么就不是一棵树，但是我们可以建立一个根结点0，让根结点指向那些a=0的点， 同时m++，因为更结点必须被占据，占据一个结点需要一个容量
每个结点可以选或者不选，但是如果选，当且仅当父亲结点也被选。
所以是树上面的01背包问题，所以只要在每个结点处枚举当前容量和孩子的容量，算出各个容量的最大值。
状态转移方程见代码
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <math.h>
using namespace std;
typedef long long LL;
const int INF = <<;
const int N = +;
struct Edge
{
int v,next;
}g[N];
int head[N],e;
int val[N];
int dp[N][N];//dp[i][j] 表示对于第i个城堡，有容量j能获得的最大价值
int n,m;
void init(int n)
{
for(int i=; i<=n; ++i)
head[i] = -;
e = ;
}
void addEdge(int a, int b)
{
g[e].v = b;
g[e].next = head[a];
head[a] = e++;
}
void dfs(int u, int fa)
{
for(int i=; i<=m; ++i)
dp[u][i] = val[u];
for(int i=head[u]; i!=-; i=g[i].next)
{
int v = g[i].v;
if(v==fa) continue;
dfs(v,u);
for(int j=m; j>=; --j)
for(int k=; k+j<=m; ++k)
dp[u][j+k] = max( dp[u][j+k], dp[u][j]+dp[v][k] );
}
}
int main()
{
int i,a,b;
while(scanf("%d%d",&n,&m),n)
{
init(n);
bool flag = false;
for(i=; i<=n; ++i)
{
scanf("%d%d",&a,&val[i]);
if(a==)
flag = true;
addEdge(i,a);
addEdge(a,i);
}
memset(dp,,sizeof(dp));
if(flag)
{
m++;
dfs(,-);
printf("%d\n",dp[][m]);
}
else
{
dfs(,-);
printf("%d\n",dp[][m]);
} }
return ;
}