以边为对象的树形DP 学习总结

一、核心思想

以边为研究对象的树形DP，关注点是树的边，但状态定义与转移仍围绕子树展开。
核心是将与边相关的问题，转化为对节点状态的决策问题，通过动态规划在树上进行状态转移求解。

二、经典树上问题模型

1. 最小点覆盖（战略游戏问题）

• 问题描述：给定无根树，士兵驻扎在点上可看守相邻边，求守住所有边的最少士兵数。
• 问题转化：每条边 $(u,v)$ 需满足 $u$ 或 $v$ 至少有一个点部署士兵。
• 状态定义
  • $dp[u][0]$：以 $u$为根的子树，$u$ 不放置士兵时的最小士兵数。
  • $dp[u][1]$：以 $u$ 为根的子树，$u$ 放置士兵时的最小士兵数。
• 状态转移
  • $dp[u][0]=\sum dp[v][1]$：$u$ 不放置士兵，子节点 $v$ 必须放置。
  • $dp[u][1]=1+\sum min(dp[v][0],dp[v][1])$：$u$ 放置士兵，子节点 $v$ 可放或不放，取最小值。

2. 最大匹配（树的匹配问题）

• 问题描述：从树中选出最多的边，使得任意两条边无公共点。
• 状态定义
  • $dp[u][0]$：以 $u$ 为根的子树，$u$ 不与子节点匹配时的最大匹配数。
  • $dp[u][1]$：以 $u$ 为根的子树，$u$ 与其中一个子节点匹配时的最大匹配数。
• 状态转移
  • $dp[u][0]=\sum max(dp[v][0],dp[v][1])$（ $v$ 为 $u$ 的子节点）：$u$ 不匹配，子节点取两种状态最大值。
  • $dp[u][1]=maxdp[vi][0]+1+\sum max(dp[vj][0],dp[vj][1])（j\ne i）$：$u$ 与某个子节点 $vi$ 匹配。
• 优化技巧
  • 利用 $dp[u][0]$ 简化计算：$dp[u][1]=max(dp[u][0]-max(dp[vi][0],dp[vi][1])+dp[vi][0]+1)$

3. 树的直径

• 定义：树上任意两节点之间的最长简单路径。
• 求解方法$1$：两次DFS/BFS法（贪心）
  1. 任选一点出发，通过DFS/BFS找到距离该点最远的点 $s$ 。
  2. 从 $s$ 出发再次DFS/BFS，找到距离 $s$ 最远的点 $t$，$s-t$ 即为直径。
  3. 适用条件：边权非负。
• 求解方法$2$：树形DP法
  • 状态定义
    • $d1[u]$：以 $u$ 为根的子树中，从 $u$ 出发向下的最长路径长度。
    • $d2[u]$：以 $u$ 为根的子树中，从 $u$ 出发向下的次长路径长度（与最长路径无重合边）。
  • 状态转移：遍历 $u$ 的子节点 $v$，计算 $len=d1[v]+w(u,v)$
    • 若 $len>d1[u]$，则 $d2[u]=d1[u]，d1[u]=len$。
    • 若 $len>d2[u]$ 且 $len\le d1[u]$，则 $d2[u]=len$。
  • 全局直径：所有节点的 $d1[u]+d2[u]$ 中的最大值。

三、重要图论定理与关系

1. Kőnig定理：二分图的最小点覆盖数 = 二分图的最大匹配数。在树上，最小点覆盖数等于最大匹配数。

2. Gallai恒等式：对于任意无向图，最小点覆盖数 + 最大独立集数 = 总顶点数 |V|。

• 点覆盖的补集是独立集，独立集的补集是点覆盖。

3. 四大经典树上问题对比

四、典型例题与应用

1. CF911F Tree Destruction：给定无权树，通过 $n-1$ 次选两个叶子、累加路径长度并删除一个叶子的操作，求最大答案并构造操作序列。核心思路是利用树的直径，优先处理非直径节点，再处理直径节点。

2. CF161D Distance in Tree：统计树上距离恰好为$ k$ 的简单路径数量。状态定义 $dp[u][j]$ 表示以 $u$ 为根的子树中到 $u$ 距离为 $j$ 的节点数，采用“先统计跨子树路径、再合并子树状态”的策略求解。

3. P3304 [SDOI2013] 直径：求树的直径长度，以及所有直径都经过的边的数量。利用直径性质：任意直径必相交，中点唯一。

五、总结

以边为对象的树形DP，可以将边的约束转化为节点的状态决策。掌握最小点覆盖、最大匹配、树的直径等经典模型的状态设计与转移，理解相关图论定理，再结合一些技巧，就能解决这类DP问题。