洛谷P2014 选课（树形DP+0/1背包）
题目的关键点是把0看作存在的节点，找到一块由0出发的连通部分（即不能出现断层）
解法一（纯递归）
要计算的是以0为根，包含0的所有子树，节点总数目为m+1的最大权值累加和，设以i为根，包含i的前j棵子树，节点总数目为k的最大权值累加和是dp[i][j][k],只需要考虑前j-1棵子树上选取s门课程，然后在第j棵子树上面选取k-s门课程，状态转移方程为
\[dp[ i ] [j][k]=max(dp[i][j-1][k-s]+dp[v][g[v].size()][s])(s从1到k，v是第j棵子树头节点，v=g[i][j-1])
\]
递归重点是k=1时或者没有子树，此时头节点的权值就是结果
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define endl '\n'
const int INF=1e18,N=301,MOD=998244353;
vector<vi> g;
int sco[N];
vector<vector<vi>> dp;
int cal(int i,int j,int k){if(k==0) return 0;if(j==0||k==1) return sco[i];if(dp[i][j][k]!=-1) return dp[i][j][k];int ans=cal(i,j-1,k);int v=g[i][j-1];for(int s=1;s<k;s++){ans=max(ans,cal(i,j-1,k-s)+cal(v,g[v].size(),s));}dp[i][j][k]=ans;return ans;
}void solve(){int n,m;cin>>n>>m;g.clear();g.resize(n+1);m++;dp.resize(n+1);for(int i=1;i<=n;i++){int k,s;cin>>k>>s;g[k].pb(i);sco[i]=s;}for(int i=0;i<=n;i++){dp[i]=vector<vi>(g[i].size()+1,vi(m+1,-1));}cout<<cal(0,g[0].size(),m)<<endl;
}signed main(){ios::sync_with_stdio(false);cin.tie(0);int T=1;// cin>>T;while(T--)solve();return 0;
}
时间复杂度为O(n*平均子树大小*m*m)
解法二（树上0/1背包）
使用DFN序，则0节点的DFN序为1,以此类推。在算DFN序的时候把其子树大小算出来，方便后续维护的连续有效结构。
以下节点以表示dfn序节点
从终点算起往回递推，设从节点i到节点n+1里面选择j门课程最大能获取dp[i][j]的学分，那么计算在dp[i+1][j]算出来后只需要考虑是否选入节点i,若选入，则在i+1号节点到n+1之间选择j-1个节点，否则i节点及其子树部分包含的节点都不可以被选入（保持连续）。两种情况取max即可，状态转移方程为
\[dp[i][j]=max(dp[i+1][j-1]+val[i],dp[i+siz[i]][j])|(siz[i]为i的子树大小，包含i)
\]
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define endl '\n'
const int INF=1e18,N=305,MOD=998244353;//DFN+树形DP
int sco[N],val[N];
int dp[N][N];
int dfncnt;
vi g[N];
int dfn[N],siz[N];//子树大小
int f(int u){//求dfn的递归函数dfn[u]=++dfncnt;int t=dfncnt;siz[t]=1;val[t]=sco[u];for(int v:g[u]){siz[t]+=f(v);}return siz[t];
}void solve(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++){int k,s;cin>>k>>s;g[k].pb(i);sco[i]=s;}f(0);for(int i=n+1;i>=2;i--){for(int j=1;j<=m;j++){dp[i][j]=max(dp[i+1][j-1]+val[i],dp[i+siz[i]][j]);}}cout<<dp[2][m]<<endl;
}signed main(){ios::sync_with_stdio(false);cin.tie(0);int T=1;// cin>>T;while(T--)solve();return 0;
}