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

考虑树形DP，这题其实是把背包搬到了树上，使得选一个物体需要经过他的前置物体才能选

那么我们只要在原有的树形DP上加一个背包即可

那么有方程，其中to是所有的儿子，第二维存的就是一维背包的东西

详细见代码...

#include<bits/stdc++.h>

using namespace std;

const int maxn=500;
int n,m;
int fa[maxn],s[maxn];
int f[maxn][maxn],tmp[maxn][maxn];

struct node{
    int to,nxt;
}tree[maxn];int head[maxn],tot;

inline void addedge(int u,int v){
    tree[++tot].to=v;
    tree[tot].nxt=head[u];
    head[u]=tot;
}

int dfs(int x){
    int sum=0;
    for(int i=head[x];i;i=tree[i].nxt){
        int t=dfs(tree[i].to);
        sum+=t+1;
        for(int j=sum;j+1;j--)
            for(int k=0;k<=t&&j-k-1>=0;k++)
                f[x][j]=max(f[x][j],f[x][j-k-1]+f[tree[i].to][k]);
    }
    return sum;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&fa[i],&s[i]);
        addedge(fa[i],i);
    }
    memset(f,0,sizeof f);
    for(int i=1;i<=n;i++) f[i][0]=s[i];
    dfs(0);
    printf("%d\n",f[0][m]);
    return 0; 
}