一般的树形背包问题，往往与以下模板异曲同工。复杂度为\(O(n^3)\)
void dfs(int u)
{
sz[u] = 1;
for(auto v:G[u])
{
dfs(v);
sz[u]+=sz[v];
for(int j=sz[u]; j>=1; --j) //滚动背包，枚举自己的所有状态
for(int k=0; k<=j; ++k) //枚举儿子的所有状态
dp[u][j] = max(dp[u][j], dp[u][k] + dp[v][j-k]); //选或不选
}
}
——上下界优化——
我们可以舍弃四个无效的状态转移：（设m为背包上限）
- j > m 的状态是无用的，因为答案不需要
- j > 当前背包容量的状态是无用的
- k至少要从 j - size[ u ] 开始 （size[ u ]是当前总节点数，尚在更新中）
- k > size[ v ]的状态是无用的
通过这四个优化，可以将时间复杂度缩短至\(O(n^2)\)！
void dfs(int u)
{
sz[u] = 1;
for(auto v:G[u])
{
dfs(v);
for(int j=min(m,sz[u]+sz[v]); j>=1; --j) //滚动背包，枚举自己的所有状态
for(int k=max(0,j-sz[u]); k<=min(j,sz[v]); ++k) //（对k加了上下界限制）枚举儿子的所有状态
dp[u][j] = max(dp[u][j], dp[u][k] + dp[v][j-k]); //选或不选
sz[u]+=sz[v]; //随后再加上
}
}
给出一棵树，求有多少种删边方案，使得删后的图每个连通块大小小于等于k，两种方案不同当且仅当存在一条边在一个方案中被删除，而在另一个方案中未被删除，答案对998244353取模。（1<=n, k<=2000）
设 \(ans[u]\) 为以节点 u 为根的子树的合法划分方案数。记录这个数据可以节省状态转移过程中的重复计算。
对于动态规划状态设计，网上的其他题解一般是：设\(dp[i][j]\)表示以节点 i 为根的子树中，连通块大小上限为 j 划分方案数。
我个人想到的状态设计：\(dp[i][j]\)表示以节点 i 为根的子树的划分方案数，其中包含根在内的连通块大小为 j 。我们不能对 j = 0作任何假设，因为这有悖于状态定义，是不合法的。因此初始化 \(dp[u][1]=1\)，表示当仅有 u 这个节点时，包含1个节点的方案数为1。随后开始枚举各儿子，讨论其边断和不断时的转移。
转移方程：
断边：\(dp[u][x] = dp[u][x]\ *\ ans[v]\)
不断边：\(dp[u][x] = dp[u][x-s]\ *\ dp[v][s]\)
void dfs(int x,int f)
{
sz[x]=1;
dp[x][1]=1;
for(int i:G[x])
{
if(i==f) continue;
dfs(i,x);
for(int j=min(k,sz[x]+sz[i]);j>0;--j) //滚动数组
{
(dp[x][j]*=ans[i])%=mod;//断边（因为是乘法，注意要先于不断边）
for(int s=max(1,j-sz[x]);s<=min(j,sz[i]);++s)
{
(dp[x][j]+=dp[x][j-s]*dp[i][s])%=mod; //不断边（此时显然不会对dp[x][1]有贡献）
}
}
sz[x]+=sz[i];
}
for(int i=1;i<=k;++i)
(ans[x]+=dp[x][i])%=mod;
}
其他做法
考虑到包含根节点在内的连通块，一定是由原树删去若干个子树得到，而这些子树又是DFS序上的连续区间，因此可以设\(dp[i][j]\) 为当前树的DFS序中，区间 1~i 所表示的连通块（也是一棵树）的合法划分数量，其中包含根节点的块的大小为 j 。 如果不选节点 i ，就意味着切去 L[ i ] ~ R[ i ] 这棵子树；若选，则进入其子树继续dp。
当然，为了保证复杂度，仍需采取上下界优化。
int up,sz[maxn],r[maxn];
int dt[maxn]; //深度
void dfs(int x,int f,int d)
{
int dfn=++up; //左端点的时间戳
dt[dfn]=d;
sz[x]=1;
for(int i:G[x])
{
if(i==f) continue;
dfs(i,x,d+1);
sz[x]+=sz[i];
}
r[dfn]=up; //右时间戳
dp[dfn][1]=1; //开始时，树体仅含本节点
for(int i=dfn;i<up;++i) //扫一遍以u为根的子树。注意是小于号
{
for(int j=max(1,dt[i+1]-d);j<=min(k,i-dfn+1);++j) //当前包含根的块的大小至少为当前点到根的距离
{
(dp[i+1][j+1]+=dp[i][j])%=mod; //选下一个节点
(dp[r[i+1]][j]+=dp[i][j]*ans[i+1])%=mod; //不选下一个节点，相当于切去这棵子树
dp[i][j]=0; //作完贡献后，顺便置零
}
}
for(int i=0;i<=min(k,sz[x]);++i)
{
(ans[dfn]+=dp[up][i])%=mod;
dp[up][i]=0;
}
}