最小顶点覆盖问题的基于树形动态规划的精确算法（树上的精确解法）

题目描述

给定一个无向树（即任意两个顶点之间有且仅有一条简单路径的连通无环图）。树中的每条边连接两个顶点。一个顶点覆盖是顶点的一个子集，使得树中的每条边至少有一个端点在该子集中。最小顶点覆盖问题是要求找出一个顶点数量最少的顶点覆盖。

这是一个经典的NP难问题在一般图上的特例。由于图的结构是树，我们可以利用其递归性质，设计一个时间复杂度为 O(n) 的动态规划算法来精确求解最小顶点覆盖的大小，并构造出对应的覆盖集合。

解题思路详解

树是一种递归结构：选定一个根节点后，整棵树可以看作根节点及其若干棵子树（每棵子树也是一棵树）构成。动态规划的核心思想是定义状态，表示以某个节点为根的子树，在满足顶点覆盖定义的条件下，其最优解（最小顶点数量）的某种情况。由于每个节点只有两种状态：在覆盖中或不在覆盖中，但其子节点的状态会受父节点状态影响，因此我们需要为每个节点设计两种状态。

第一步：定义状态与状态转移

我们任选一个节点（比如节点1）作为整棵树的根，将无根树转化为有根树。

对于以节点 u 为根的子树，我们定义两个状态：

• dp[u][0]：表示在以 u 为根的子树中，不选择节点 u 进入顶点覆盖的情况下，覆盖该子树所有边所需的最小顶点数。
• dp[u][1]：表示在以 u 为根的子树中，选择节点 u 进入顶点覆盖的情况下，覆盖该子树所有边所需的最小顶点数。

我们的目标是求出 min(dp[root][0], dp[root][1])。

状态转移分析：

1. 当选择节点 u 时（即计算 dp[u][1]）：

   • 节点 u 已经被选入覆盖，那么它与所有子节点 v 相连的边都已经被 u 覆盖了。因此，对于子节点 v 本身，可以选择放入覆盖或不放入覆盖，没有强制约束。我们应该为每棵子树选择代价较小的方案。
   • 转移方程：dp[u][1] = 1 + Σ min(dp[v][0], dp[v][1])，其中 v 是 u 的所有子节点，1 代表选择了节点 u 本身。

2. 当不选择节点 u 时（即计算 dp[u][0]）：

   • 节点 u 不在覆盖中。那么，为了覆盖边 (u, v)，节点 v 必须被选入覆盖。因为如果 v 也不在覆盖中，这条边就没有任何端点被覆盖，违反了顶点覆盖的定义。
   • 因此，对于每个子节点 v，我们必须选择 dp[v][1]。
   • 转移方程：dp[u][0] = Σ dp[v][1]。

边界条件：

• 当 u 是叶子节点时，它没有子节点。
  • dp[u][0] = 0。解释：不选叶子节点 u，且没有边需要覆盖（因为考虑以 u 为根的子树，只有节点 u 自己，没有边），所以所需顶点数为0。
  • dp[u][1] = 1。解释：选择叶子节点 u，顶点数计数为1。

第二步：算法过程与伪代码

我们可以通过一次深度优先搜索（DFS）自底向上地计算所有节点的 dp 值。因为树有 n 个节点，n-1 条边，所以时间复杂度是 O(n)。伪代码如下：

// 假设树的邻接表为 graph，节点编号 1..n
// visited 数组用于DFS

function DFS(u, parent):
    // 初始化叶子节点的情况（会被子节点遍历覆盖）
    dp[u][0] = 0
    dp[u][1] = 1

    for each v in graph[u]:
        if v == parent: continue // 避免回到父节点
        DFS(v, u) // 递归处理子节点
        // 回溯时，根据状态转移方程更新
        dp[u][0] += dp[v][1]
        dp[u][1] += min(dp[v][0], dp[v][1])

计算结束后，答案就是 min(dp[root][0], dp[root][1])。

第三步：构造具体的最小顶点覆盖集合

动态规划通常只给出最优解的值，但我们可以通过存储额外的信息来还原出具体的覆盖集合。我们可以再执行一次DFS，从根节点开始，根据 dp 值做决策，判断每个节点是否应该被选入覆盖。

定义递归函数 construct(u, parent, must_cover)，其中 must_cover 是一个布尔值，指示在当前决策路径下，节点 u 是否必须被覆盖（即，如果 u 的父节点没有被选，那么 u 就必须被选，以确保它们之间的边被覆盖）。

但更直观的方法是，在第一次DFS完成后，我们从根节点开始再做一次自上而下的推导：

• 对于根节点 root，我们看 dp[root][0] 和 dp[root][1] 哪个小，就选择对应的状态。如果两者相等，任选其一（比如选择 dp[root][1]，即选根节点，可以让覆盖集合可能更平均）。
• 假设当前节点 u 的状态是已知的（即我们知道在最优解中，u 是被选还是不选），那么我们可以决定其子节点的状态：
  1. 如果 u 被选了（状态1），那么对于子节点 v，在最优解中它可以是状态0或状态1，我们选择使得 dp[v] 值更小的那个。即，如果 dp[v][0] < dp[v][1]，则在最优解中 v 是状态0（不被选）；否则是状态1（被选）。
  2. 如果 u 没被选（状态0），那么根据之前的转移方程，子节点 v 在最优解中必须是状态1（被选）。

伪代码（还原覆盖集合）：

cover_set = [] // 存储最终的最小顶点覆盖

function build(u, parent, state):
    // state 表示节点 u 在最优解中的状态：0-不选，1-选
    if state == 1:
        将 u 加入 cover_set
    for each v in graph[u]:
        if v == parent: continue
        if state == 0:
            // u 没选，v 必须选
            build(v, u, 1)
        else: // state == 1
            // u 选了，v 可选可不选，取最优
            if dp[v][0] < dp[v][1]:
                build(v, u, 0)
            else:
                build(v, u, 1)

// 调用
root = 1
if dp[root][0] < dp[root][1]:
    build(root, -1, 0)
else:
    build(root, -1, 1)

第四步：举例说明

考虑一棵简单的树：4个节点，边为 (1-2), (1-3), (2-4)。
我们以节点1为根。

1. 叶子节点：节点3和节点4。
   • 节点3: dp[3][0]=0, dp[3][1]=1
   • 节点4: dp[4][0]=0, dp[4][1]=1
2. 节点2（孩子是4）：
   • dp[2][0] = dp[4][1] = 1
   • dp[2][1] = 1 + min(dp[4][0], dp[4][1]) = 1 + min(0,1) = 1
3. 根节点1（孩子是2和3）：
   • dp[1][0] = dp[2][1] + dp[3][1] = 1 + 1 = 2
   • dp[1][1] = 1 + min(dp[2][0],dp[2][1]) + min(dp[3][0],dp[3][1]) = 1 + min(1,1) + min(0,1) = 1+1+0 = 2
     最小值为2。两种状态都能得到大小2的最小覆盖。

如果选择根节点状态1（选节点1）：

• 节点2: dp[2][0]=1, dp[2][1]=1，相等，假设我们选节点2（状态1）。
• 节点3: dp[3][0]=0 < dp[3][1]=1，所以不选节点3。
• 节点4: 节点2选了，所以节点4可不选（因为dp[4][0]=0 < dp[4][1]=1）。
  得到覆盖集合 {1, 2}。检查：边(1-2)被1、2覆盖；(1-3)被1覆盖；(2-4)被2覆盖。正确。

如果选择根节点状态0（不选节点1）：

• 那么节点2和节点3都必须被选（因为它们的父节点1没选）。
• 节点2被选，对于节点4，必须被选（因为父节点2被选，但这是“必须”吗？等一下，这里容易出错。我们重新按照规则来：节点1状态0，所以子节点2和3必须状态1。节点2状态1，对于子节点4，可以选择状态0或1，选最优的。dp[4][0]=0, dp[4][1]=1，所以节点4应该状态0不选）。
  得到覆盖集合 {2, 3}。检查：边(1-2)被2覆盖；(1-3)被3覆盖；(2-4)被2覆盖。正确。

两种覆盖 {1,2} 和 {2,3} 都是最小顶点覆盖，大小都为2。

总结

这个算法充分利用了树的递归结构，通过定义每个节点“选”与“不选”两种状态，并分析父子节点状态间的约束关系，实现了线性时间复杂度的精确求解。它不仅适用于求最小顶点覆盖的大小，还能通过回溯构造出具体的覆盖集合。这是动态规划在树形结构上应用的经典范例。