题目大意就不说了
直接DP[i][j]表示i为跟节点的子树上攻克j个城堡的所能获得的最多宝物的数量
DP[fa][j] = MAX{DP[fa][i-k] + DP[child][k]};
首先一个问题就是说如果子树u下的任意子节点被选择了，那么u是一定需要选择的，怎么在DP时保证准确性，其实这个很好解决，我们在计算时是需要枚举k（子节点的攻克数量）的，那么我们迫使k<j就可以了，这样的话DP[fa][j] 就不会被子节点的DP[child][j]更新掉保证了他的父节点一定在被选择的里面
另外一个问题就是如果枚举j时是从小到达枚举，那么DP[fa][j]很可能已经被当前的child更新过了，那么在计算DP[fa][j+1]或者以后时，很可能有会被放入同一个child，导致当前的child被选择了多次，所以我们需要逆序枚举j(k的顺序无关紧要了)
最后的结果就是个棵树上同样取DP值，只是一颗完整的树上可以一个也不取了
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define INF ((LL)100000000000000000)
#define inf (-((LL)1<<40))
#define lson k<<1, L, mid
#define rson k<<1|1, mid+1, R
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define mem(a, b) memset(a, b, sizeof(a))
#define FOPENIN(IN) freopen(IN, "r", stdin)
#define FOPENOUT(OUT) freopen(OUT, "w", stdout)
template<class T> T CMP_MIN(T a, T b) { return a < b; }
template<class T> T CMP_MAX(T a, T b) { return a > b; }
template<class T> T MAX(T a, T b) { return a > b ? a : b; }
template<class T> T MIN(T a, T b) { return a < b ? a : b; }
template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }
template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b; } //typedef __int64 LL;
typedef long long LL;
const int MAXN = ;
const int MAXM = ;
const double eps = 1e-;
int dx[] = {-, , , };
int dy[] = {, -, , }; int N, M;
int G[MAXN][MAXN], vis[MAXN], num[MAXN];
int DP[MAXN][MAXN], D[MAXN]; void DFS(int u)
{
vis[u] = ;
DP[u][] = num[u];
for(int i=;i<=N;i++) if(G[u][i])
{
if(!vis[i]) DFS(i);
for(int j=M;j>;j--)//这里为了保证是先从父节点更新，需要逆序
for(int k=;k<j;k++)//k<j保证父节点不会被更新掉
DP[u][j] = MAX(DP[u][j], DP[u][j-k] + DP[i][k]);
}
} int main()
{
//FOPENIN("in.txt");
while(~scanf("%d %d", &N, &M) &&( N||M))
{
int a;mem0(G);mem0(D);mem0(vis);mem0(DP);
for(int i=;i<=N;i++) {
scanf("%d %d", &a, &num[i]);
if(a != )G[a][i] = ;
else D[i] = ;
}
for(int i=;i<=N;i++) if(!vis[i]){
DFS(i);
if(D[i]) for(int j=M;j>=;j--)//同样需要逆序，可以取到0
{
for(int k=;k<=j;k++)
DP[][j] = MAX(DP[][j], DP[][j-k] + DP[i][k]);
}
}
printf("%d\n", DP[][M]); }
return ;
}