树形DP入门讲解附例题一、什么是树形DP树形动态规划树形DP是在树结构上进行的动态规划算法核心是利用树的父子层级关系通过深度优先搜索DFS后序遍历先计算所有子节点的状态再推导父节点的状态自底向上求解整棵树的最优解。树形DP最经典、最基础的题型是节点“选/不选”二元状态模型即对每个节点定义两种状态选或不选该节点再根据题目约束推导状态转移方程。常见的这类问题包括最小点覆盖、最大独立集、树上打家劫舍等。二、基础模型树的最小点覆盖问题定义给定一棵树选择最少的节点使得树上的每一条边都至少有一个端点被选中。这个最少节点数就是树的最小点覆盖。状态定义我们对每个节点u定义两个状态dp[u][0]不选节点u时以u为根的子树的最小点覆盖数dp[u][1]选节点u时以u为根的子树的最小点覆盖数状态转移方程对于节点u及其子节点v如果选uu-v这条边已经被u覆盖因此子节点v可以选也可以不选我们取子树的最优值d p [ u ] [ 1 ] min ( d p [ v ] [ 0 ] , d p [ v ] [ 1 ] ) dp[u][1] \min(dp[v][0],\ dp[v][1])dp[u][1]min(dp[v][0],dp[v][1])初始时dp[u][1] 1选自己计数1。如果不选uu-v这条边必须由子节点v来覆盖因此v必须被选中d p [ u ] [ 0 ] d p [ v ] [ 1 ] dp[u][0] dp[v][1]dp[u][0]dp[v][1]初始时dp[u][0] 0不选自己计数为0。遍历方式通过 DFS 后序遍历先递归处理所有子节点得到子节点的 dp 值后再更新父节点的 dp 值。最终整棵树的最小点覆盖为min(dp[root][0], dp[root][1])。三、例题实战小红的树权值题目链接牛客竞赛 - 小红的树权值题意转化题目定义树的权值删除若干节点后剩余所有连通块大小都为1求最小删除数量。我们可以把问题等价转化为剩余连通块大小都为1 → 剩余的任意两个点之间都没有边相连 → 树上每条边至少有一个端点被删除。因此最小删除数量 这棵树的最小点覆盖数。题目要求输出每个节点的子树的权值即求以每个节点为根的子树的最小点覆盖。解法思路由于题目已经给出以1号节点为根的有根树我们只需要进行一次后序DFS递归计算每个子节点的dp[0/1]每个节点的子树权值就是min(dp[u][0], dp[u][1])最终按顺序输出1~n号节点的结果即可参考代码与解析#includebits/stdc.husingnamespacestd;constintN1e59;intdp[N][2];// dp[u][0]:删除u; dp[u][1]:不删除uvectorintg[N];// 邻接表存树voiddfs(intnow,intfa){dp[now][0]1;// 删除当前节点初始计数为1dp[now][1]0;// 不删除当前节点初始计数为0for(intnt:g[now]){if(ntfa)continue;// 跳过父节点dfs(nt,now);// 先递归处理子节点// 当前节点不删除 → 子节点必须删除才能覆盖边dp[now][1]dp[nt][0];// 当前节点删除 → 子节点删或不删都可以取最小值dp[now][0]min(dp[nt][0],dp[nt][1]);}}intmain(){ios::sync_with_stdio(false);cin.tie(0);intt;cint;while(t--){intn;cinn;// 多组数据清空邻接表for(inti1;in;i)g[i].clear();for(inti1;in;i){intu,v;cinuv;g[u].push_back(v);g[v].push_back(u);}dfs(1,0);// 从根节点1开始DFS// 输出每个节点子树的最小删除数for(inti1;in;i){coutmin(dp[i][0],dp[i][1]) ;}cout\n;}return0;}样例验证输入样例1 5 1 2 2 3 3 4 3 5树的结构1-2-33连接4和5。节点4、5是叶子删除自己为1不删除为0 → 答案0不删更优。节点3删的话代价1 子节点都不删(00) 1不删的话代价0 子节点都删(11) 2 → 答案1。节点2删的话代价1 min(1,2) 2不删的话代价0 1 1 → 答案1。节点1删的话代价1 min(1,2) 2不删的话代价0 1 2 → 答案2。输出2 1 1 0 0与样例完全一致。四、总结树形DP的核心是状态定义和转移方程入门阶段优先掌握“选/不选”二元状态模型。实现上通常用DFS后序遍历子节点状态计算完成后再更新父节点。遇到树上“选最少点覆盖边”“选最多不相邻点”类问题可以优先考虑最小点覆盖、最大独立集模型快速转化为树形DP求解。五、真题实战[蓝桥杯 2025 省 B] 生产车间https://www.luogu.com.cn/problem/P12136正解代码#includebits/stdc.husingnamespacestd;constintN1010;intn,w[N];booldp[N][N];vectorintg[N];//dp[i][j] 节点为i 重量为j 是否可达voiddfs(intnow,intfa){//当前节点 父节点for(autont:g[now]){if(ntfa)continue;dfs(nt,now);//01for(intjw[now];j0;j--){for(intkw[nt];k0;k--){if(jkw[now])dp[now][jk]|(dp[now][j]dp[nt][k]);//因j与k的不同组合 可能jk相同 so | 而不是 }}}}intmain(){cinn;for(inti1;in;i)cinw[i];for(inti1;in;i){intu,v;cinuv;g[u].push_back(v);g[v].push_back(u);}for(inti1;in;i){//初始化dp[i][0]1;//不装if(i1g[i].size()1)//叶子节点dp[i][w[i]]1;//本身}dfs(1,0);for(intjw[1];j0;j--){if(dp[1][j]){coutj;break;}}return0;}
