一道经典树形dp，你会了二叉苹果树那么这个也会了

细节已写在代码里,一定要清楚设的变量和函数的含义

code

#include<bits/stdc++.h>
using namespace std;
int s[305]={0};
vector<int> son[305];
int ans[305][305]={0};
int n,m;
void ss(int now)
{
    for(int i=0;i<son[now].size();i++)
    {
        int next=son[now][i];
        ss(next);
        for(int k=m;k>=1;k--)
            for(int j=0;j<k;j++)//为什么不用min(k,son[next].size()+1)呢，因为son...仅仅求了next的子节点的个数而非以next为根的树的节点个数，反正就算k大于总结点个数也是零，肯定小
                ans[now][k]=max(ans[now][k],ans[now][k-j-1]+ans[next][j]+s[next]);//为什么一定要选next课？如果不选说明学分小，把学分小和选合在一块操作了，经典背包
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int fa;
        cin>>fa>>s[i];
        son[fa].push_back(i);//构建虚拟根节点，就变成了树
    }
    ss(0);
    cout<<ans[0][m];//ans[i][j]代表选了i课后再选m个课的学分最大值（再选，自然不包括i）
    return 0;
}