E18 树形DP 树上背包 P2014 [CTSC1997] 选课
标程：

using namespace std;
const int N=300,M=300; // 修正原代码中N=M=310可能的笔误，实际题目n,m可能为300级别
int n,m,pool[N*M],w[N],v[N],siz[N],rdfn[N],id;
vector<int>f[N],G[N];
void dfs(int x)
{
    siz[x]=1;
    for(auto y:G[x]) dfs(y),siz[x]+=siz[y];
    rdfn[++id]=x;
}
signed main() {
    ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
    cin>>n>>m;
    int (&f)[n+2][m+1]=decltype(f)(pool);
    for(int i=1,x;i<=n;++i) cin>>x>>v[i],w[i]=1,G[x].push_back(i);
    id=0;dfs(0); // dfs(0)作为虚拟根节点
    for(int i=1;i<=id;++i) {
        int x=rdfn[i];
        for(int j=0;j<=m;++j) {
            f[i][j]=f[i-siz[x]][j];// 继承父节点状态
            if(j>=w[x]) f[i][j]=max(f[i][j],f[i-1][j-w[x]]+v[x]);// 选择当前节点
        }
    }
    cout<<f[id][m]<<'\n';
    return 0;
}

旧代码：

using namespace std;

struct trnode {
    int lc,rc,c,lastc;//lastc等于0表示没有孩子来报到，不等于0表示当前报到的最后一个孩子 
    trnode(){lc=rc=lastc=0;}
}tr[1100];
 
int f[1100][1100];//f[i][j]表示i为根节点，保留j个点的最大值(包括i)
void treedp(int x,int k)//x表示节点，k表示保留节点数
{
    if(f[x][k]!=-1)return ;//已计算过
    int maxs=0;
    for(int rs=0;rs<=k;rs++){//右子树保留rs个节点
        int ls=k-rs-1;//左子树保留ls个节点，当前节点占1个
        int fls=0,frs=0,lc=tr[x].lc,rc=tr[x].rc;
        if(ls>=0) {treedp(lc,ls); fls=f[lc][ls];}
        treedp(rc,rs); frs=f[rc][rs];//右子树rs个节点
        maxs=max(maxs, fls+frs+tr[x].c);
    }
    f[x][k]=maxs;
}
int main() {
    int n,K;scanf("%d%d",&n,&K);K++;
    for(int i=1;i<=n;i++) {
        int x,c;scanf("%d%d",&x,&tr[i].c);if(x==0)x=n+1;
        if(tr[x].lastc==0) tr[x].lc=i;
        else tr[tr[x].lastc].rc=i;
        tr[x].lastc=i;
    }
    memset(f,-1,sizeof(f));
    for(int i=0;i<=n+1;i++)f[i][0]=0;
    treedp(n+1,K);
    printf("%d\n",f[n+1][K]);
    return 0;
}

E18 树形DP 树上背包 P2014 [CTSC1997] 选课
标程：

#include<bits/stdc++.h>
using namespace std;
const int N=310,M=310;
int n,m,pool[N*M],w[N],v[N],siz[N],rdfn[N],id;
vector<int>f[N],G[N];
void dfs(int x)
{
    siz[x]=1;
    for(auto y:G[x]) dfs(y),siz[x]+=siz[y];
    rdfn[++id]=x;
}
signed main()
{
    ios::sync_with_stdio(False);cin.tie(0),cout.tie(0);
    cin>>n>>m;
    int (&f)[n+2][m+1]=decltype(f)(pool);
    for(int i=1,x;i<=n;++i) cin>>x>>v[i],w[i]=1,G[x].push_back(i);
    id=0;dfs(0);
    for(int i=1;i<=id;++i)
	{
        int x=rdfn[i];
        for(int j=0;j<=m;++j)
		{
            f[i][j]=f[i-siz[x]][j];//秒 
            if(j>=w[x]) f[i][j]=max(f[i][j],f[i-1][j-w[x]]+v[x]);
        }
    }
    cout<<f[id][m]<<'\n';
    //cerr<<"Running Time: "<<(double)clock()/CLOCKS_PER_SEC<<" s\n";
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
struct trnode
{
int lc,rc,c,lastc;//lastc等于0表示没有孩子来报到，不等于0表示当前报到的最后一个孩子
trnode(){lc=rc=lastc=0;}
}tr[1100];
int f[1100][1100];//f[i][j]表示i为根节点，保留j个点的最大值(包括i)
void treedp(int x,int k)//x表示到哪个节点了，y表示这个节点能保存的最大值
{
if(f[x][k]!=-1)return ;//计算过了就不需要再计算
int maxs=0;
for(int rs=0;rs<=k;rs++)
{
int ls=k-rs;//左边的任务以及右边的任务
int fls,frs,lc=tr[x].lc,rc=tr[x].rc;
if(ls>=1){treedp(lc,ls-1); fls=f[lc][ls-1]+tr[x].c;} else fls=0;
treedp(rc,rs); frs=f[rc][rs];
    maxs=max(maxs&#44; fls+frs );
}
f[x][k]=maxs;

}
int main()
{
int n,K;scanf("%d%d",&n,&K);K++;
for(int i=1;i<=n;i++)
{
int x,c;scanf("%d%d",&x,&tr[i].c);if(x0)x=n+1;
if(tr[x].lastc0) tr[x].lc=i;
else    tr[ tr[x].lastc ].rc=i;
tr[x].lastc=i;
}
memset(f,-1,sizeof(f));
for(int i=0;i<=n+1;i++)f[i][0]=f[0][i]=0;
treedp(n+1,K);
printf("%d\n",f[n+1][K]);
return 0;
}