AcWing1077-cnblog

问题背景

给定一个树形结构的图，每个节点代表一个地点，每个节点有一个守卫的代价。我们希望以最低的代价在树的节点上放置守卫，使得整棵树的所有节点都被监控。可以通过三种方式覆盖一个节点：

1. 由父节点监控。
2. 由子节点监控。
3. 自己放置一个守卫监控自己。

状态表示

定义 $ f[i][k] $ 为第 $ i $ 个节点在状态 $ k $ 下的最小代价，其中状态 $ k $ 有三种取值：

• $ f(i, 0) $：第 $ i $ 号节点由父节点的守卫监控的方案数。
• $ f(i, 1) $：第 $ i $ 号节点由子节点的守卫监控的方案数。
• $ f(i, 2) $：第 $ i $ 号节点自己放置守卫监控自己的方案数。

状态转移方程

根据题意和约束条件，通过递归计算以下三种状态的最小代价：

1. 父节点监控 $ f(i, 0) $：节点 $ i $ 被父节点监控，则每个子节点 $ j $ 要么自己监控自己（状态 $ f(j, 2) $），要么被它的子节点监控（状态 $ f(j, 1) $）。
   $$f(i,0)=\sum \min (f(j,1),f(j,2))$$

2. 子节点监控 $ f(i, 1) $：节点 $ i $ 被一个子节点监控。我们要枚举是哪一个子节点 $ k $ 来监控 $ i $，然后在所有方案中取最小值。
   f ( i , 1 ) = min ⁡ k { f ( i , 0 ) + f ( k , 2 ) − min ⁡ ( f ( k , 1 ) , f ( k , 2 ) ) } f(i, 1) = \min_{k} \{ f(i, 0) + f(k, 2) - \min(f(k,1), f(k,2)) \} f(i,1)=kmin​{f(i,0)+f(k,2)−min(f(k,1),f(k,2))}
   其中， $ f(i, 0) $ 中包含了所有子节点的最小监控代价之和，这里要去除子节点 $ k $ 的原代价，替换成状态 $ f(k, 2) $（即子节点 $ k $ 自己监控自己）。

3. 自我监控 $ f(i, 2) $：节点 $ i $ 自己放置守卫，则所有子节点 $ j $ 可以选择任意一种监控方案：由父节点监控、自己监控或由子节点监控。
   $$f(i,2)=\sum \min (f(j,0),f(j,1),f(j,2))+w(i)$$
   其中， $ w(i) $ 表示在节点 $ i $ 放置守卫的代价。

算法流程

1. 建树：使用邻接表存储树结构，使用 add 函数建立节点之间的连接。
2. 找到根节点：在输入数据中标记所有有父节点的节点，剩下未标记的节点即为根节点。
3. 深度优先搜索 (DFS)：从根节点开始递归遍历树，计算每个节点的三种状态的最小代价。
4. 结果输出：最终输出根节点的两种监控方案中的最小代价，即 min(f[root][1], f[root][2])。

代码中的核心部分

• dfs(int u)：递归计算每个节点在三种状态下的最小代价。利用递归遍历树的结构，自底向上地计算各个状态的代价。
• add(int a, int b)：构建树的邻接表表示，用于方便地遍历子节点。
• 状态初始化和递推公式的应用：在 DFS 的过程中，不断更新和计算 f[u][0], f[u][1], f[u][2]。

复杂度分析

由于是树形结构的遍历，算法的时间复杂度为 $ O(N) $，其中 $ N $ 是节点数。空间复杂度同样是 $ O(N) $，主要用于存储树的结构和每个节点的三种状态的代价。

总结

• 这个算法有效利用了树的层次结构和动态规划的递推思想，通过状态转移和自底向上的动态规划求解每个节点的最小监控方案。

• 状态设计和转移公式充分考虑了监控的三种情况，通过分解为子问题并合并结果，实现了最优代价的计算。

• 状态设计和转移公式充分考虑了监控的三种情况，通过分解为子问题并合并结果，实现了最优代价的计算。

这段代码是一个典型的树形动态规划问题的解法，适用于解决诸如最小路径覆盖、监控覆盖等类似的树结构上的最小代价问题。