动态规划贩卖机

树形dp

树上背包

洛谷2014 选课

// 树上背包
// 关系构成一个DAG图，又每个点只有一个父亲，构成一个森林
// 每棵子树，要想选孩子，根节点是必须要选的。
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int maxn = 305;
vector<vector<int> >G;
int dp[maxn][maxn]; // 到第i号为根的子树中，已经遍历了i号点的前j棵子树，选了k门课的最大学分
int sz[maxn];
// 此处空间优化了第二维

void dfs(int u){
    sz[u]=1;
    for(auto v:G[u]){
        dfs(v);
        sz[u]+=sz[v];
        for(int j=m+1;j>=1;--j){
            // 当前已经选了j
            for(int k=0;k<=sz[v]&&j-k>0;++k){
                // 当前子树选k个
                dp[u][j] = max(dp[u][j-k]+dp[v][k],dp[u][j]);
            }
        }
    }
}

void solve(){
    dfs(0);  // 答案为m+1是因为，空的根节点必选，而这个节点是捏造的
    cout<<dp[0][m+1]<<endl;
}

int main(){
    scanf("%d%d",&n,&m);
    G.resize(n+4);
    for(int i=1;i<=n;++i){
        int u,w;scanf("%d%d",&u,&w);
        G[u].push_back(i);
        dp[i][1] = w;
    }
    solve();
}