原题链接：https://www.luogu.com.cn/problem/P2014

树上背包问题

主要的思想就是利用课程的前置课程只有一个或没有来构造一棵树。然后利用选课的数目进行更新来实现类似于01背包的dp规律。

#include <iostream>
#include <vector>

#define ll long long

const ll N = 1e3;
ll n,m;
ll op[N][N];
std::vector<ll> dp[N];
bool pp[N];
//ll cnt = 0;

ll dfs(ll aa){
    ll cnt = 1;
    for(auto jj : dp[aa]){
        ll kk = dfs(jj);
        for(ll i = std::min(m,cnt); i >= 1; i --){//和01背包一样，总重从大到小遍历
            for(ll j = 1,h = std::min(kk,m - i); j <= h; j ++){
                op[aa][i + j] = std::max(op[aa][i + j],op[aa][i] + op[jj][j]);
            }
        }
        cnt += kk;
    }
    return cnt;
}

void solve(){
    std::cin >> n >> m;
    for(ll i = 1; i <= n; i ++){
        ll a,b;
        std::cin >> a >> b;
        dp[a].push_back(i);//构造树没有前置课程的连接到0
        op[i][1] = b;//第i门科目开始选一个科目就是自己本身
    }
    m ++;//不能够缺
    dfs(0);//从0开始
    std::cout  << op[0][m] << "\n";
    return ;
}

int main(){
    ll t = 1;
    while(t --)
    solve();
    return 0;
}