2026-02-02
1 以点为对象的树形DP
1.1 最大独立集
例题 ： Luogu： P1352 没有上司的舞会
1.1.1 状态定义
- \(dp[u][0]\)：不选节点 \(u\) 时，以 \(u\) 为根的子树的最大权值和
- \(dp[u][1]\)：选中节点 \(u\) 时，以 \(u\) 为根的子树的最大权值和
1.1.2 转移方程
- 若选中 \(u\)：子节点 \(v\) 必须不选，累加所有子节点的 \(dp[v][0]\) ，再加上自身权值
- 若不选 \(u\)：子节点 \(v\) 可选或不选，取两者最大值累加
1.1.3 代码实现
点击查看代码
void dfs(int u,int f){dp[u][0]=0;dp[u][1]=a[u];for(auto v:input[u]){if(v==f) continue;dfs(v,u);dp[u][1]+=dp[v][0];dp[u][0]+=max(dp[v][0],dp[v][1]);} }
1.2 最小支配集
例题 ： Luogu： P2458 [SDOI2006] 保安站岗
1.2.1 状态定义
需要区分 “覆盖来源”，因此定义 3 种状态：
- \(dp[u][0]\)：\(u\) 被选中（可覆盖自身及子节点）；
- \(dp[u][1]\)：\(u\) 未选中，但被至少一个子节点覆盖；
- \(dp[u][2]\)：\(u\) 未选中，依赖父节点覆盖。
1.2.2 转移方程
简单：
- \(dp[u][0]\)：\(u\) 选中，子节点可任意状态，取最小值累加
- \(dp[u][2]\)：\(u\) 依赖父节点，子节点必须被自身或其子节点覆盖
困难：
- \(dp[u][1]\)：\(u\) 被子节点覆盖？ 似乎不好转移，不如先让子节点中至少有一个被选中？！
\(dp[u][1]\)：需确保至少一个子节点选中。先累加所有子节点的 \(min(dp[v][0],dp[v][1])\)，若没有子节点选中，则强制替换一个成本最小的子节点的状态为\(dp[v][0]\)
1.2.3 技巧总结
通过 “标记是否有子节点选中” 和 “计算最小替换成本” 避免后效性，确保状态转移的正确性。
1.2.4 扩展问题
例题 ： Luogu： P2279 [HNOI2003] 消防局的设立
当覆盖范围扩大，状态定义需扩展为 5 种
覆盖来源：自身、儿子、孙子、父亲、爷爷
核心思路是 “枚举所有覆盖可能性，确保子树全覆盖”。这种思想可推广到更复杂的覆盖问题。
2 以边为对象的树形DP
2.1 最小点覆盖
例题 ： Luogu： P2016 [SEERC 2000] 战略游戏
2.1.1 问题转化
边的覆盖本质是 “端点的选择”：对于边 \((u, v)\)，\(u\) 或 \(v\) 至少选一个。因此问题可转化为 “最小点覆盖”—— 选择最少的点，覆盖所有边。
2.1.2 状态定义
- \(dp[u][0]\)：\(u\) 不选士兵，以 \(u\) 为根的子树覆盖所有边的最少士兵数（此时子节点 v 必选）
- \(dp[u][1]\)：\(u\) 选士兵，以 \(u\) 为根的子树覆盖所有边的最少士兵数（此时子节点 v 可选）
2.2 最大匹配
2.2.1 问题描述
选择最多的边，使任意两条边无公共节点
2.2.2 状态定义
- \(dp[u][0]\)：\(u\) 不与任何子节点匹配，以 \(u\) 为根的子树的最大匹配数
- \(dp[u][1]\)：\(u\) 与某个子节点匹配，以 \(u\) 为根的子树的最大匹配数
2.2.3 转移方程
- \(dp[u][0]\)：子节点 \(v\) 可匹配或不匹配，取最大值累加
- \(dp[u][1]\)：选择一个子节点 \(v_i\) 与 \(u\) 匹配，\(v_i\) 必须不与它的子节点匹配，其他子节点取最大值
3 四种经典问题的异同
概念 对象 约束 目标 比喻 最大独立集 (Independent Set) 点 选出的点两两不相邻 最大化 不邀请仇人 (要求大家都互不认识) 最小支配集 (Dominating Set) 点 图中每一个点 要么被选，要么邻居被选 最小化 建基站 (所有城市都有信号) 最小点覆盖 (Vertex Cover) 点 图中每一条边 至少有一个端点被选中 最小化 街道巡逻 (监控所有街道) 最大匹配 (Matching) 边 选出的边两两不共点 最大化 相亲大会 (一人只能结一次婚)