题解|算法竞赛进阶指南 选课

树形dp模板题
首先建一个虚拟节点0，让原本的森林变成一颗树。
然后我们设dp[i][j]表示以i为根的子树中,选j门课的最大价值。
转移时我们枚举当前以x为根的子树选课的数量(t)，以及分配给x的子节点y多少节课(j)。
不难写出方程：dp[x][t]=max(dp[x][t],dp[x][t-j]+dp[y][j]);

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=510;
const ll INF=2147483647;
ll n,m,s,a[maxn],dp[maxn][maxn];
vector<ll> e[maxn];
void work(ll x){
    dp[x][0]=0;
    for(int i=0;i<e[x].size();i++){
        work(e[x][i]);
        for(int t=m;t>=0;t--){
            for(int j=t;j>=0;j--){
                dp[x][t]=max(dp[x][t],dp[x][t-j]+dp[e[x][i]][j]);
            }
        }
    }
    if(x){//x不为0时，选修x需要占用一门课，获得相应学分.
        for(int i=m;i>0;i--){
            dp[x][i]=dp[x][i-1]+a[x];
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s>>a[i];
        if(s==0)e[0].push_back(i);//虚拟节点
        else e[s].push_back(i);
    }
    work(0);
    cout<<dp[0][m];
    return 0;
}