Solution
我们发现本题中有好多主从关系，即要想取用一个儿子必须先取用她的父亲。构成了一个森林，处理不便。
有个小技巧，就是将0号节点参与建树，最后所求节点数就变成了\(m+1\)，且把森林变成了一棵树。
然后如何处理呢？
再次理解题意，我们发现，我们每次的决策是是否取用儿子，取用几个儿子......这不就是背包模型？对于每个父节点，先搜她的儿子，然后枚举重量(从\(m+1\)到1，和01背包同理，每个儿子只能选一次)，再枚举每个儿子内又取几个儿子......由于我们先前先搜的儿子，我们确保搜到这里儿子是已知的。
形式化地，若令\(f_{now,j}\)表示以\(now\)为父节点选\(j\)个课时的最大价值，则有：
\(f_{now,j} = max(f_{now,j},f_{Edge_{now,i},k}+f_{now,{j-k}})\)
explanation:\(Edge_{now,i}\)表示节点\(now\)的第\(i\)个儿子，容易发现这里运用了vector建树。形象地就是取\(k\)个儿子和原来的决策取max
Code
/*
树上dp，渗透了背包的思想。
小技巧：我们发现本题有好多树，构成森林，我们可以把0号节点也参与建树，这样就把森林变成了一棵树。
对于一个父节点，她可以选or不选以及选几个儿子学习，发现这可以当作背包，类似于背包从大到小枚举m也就是选的节点数（可以看作重量）
枚举完重量再枚举选儿子，状态转移方程和背包类似。
运用小技巧将森林变成树后记得m+1
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define N 1010
using namespace std;
int n,m;
int f[N][N];
vector <int> Edge[N];
void dp(int now)
{
for(int i=0;i<Edge[now].size();i++)
{
dp(Edge[now][i]);//先处理儿子
for(int j=m;j>=1;j--)
{
for(int k=0;k<j;k++)
{
f[now][j] = max(f[now][j],f[Edge[now][i]][k]+f[now][j-k]);//状态转移，取or不取or取几个儿子的儿子（儿子已经处理好）
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
int fa;
scanf("%d%d",&fa,&f[i][1]); //以每个节点为父亲选一个肯定是其本身，直接输入即可
Edge[fa].push_back(i);
}
m++;//更新m
dp(0);
cout<<f[0][m]<<endl;//注意到我们这里将0号节点参与建树，所以输出的时候需要注意
return 0;
}