题解

发射器 题解

问题分析

我们有一棵 $n$ 个节点的树，需要在节点上放置发射器，使得每条边 $(u,v)$ 满足：

1. $u$ 或 $v$ 有发射器，或者
2. $u$ 或 $v$ 的邻居中（包括自身）至少有 2 个发射器

这是一个树上的覆盖问题，类似于最小支配集但条件更复杂。

关键观察

覆盖条件分析

对于边 $(u,v)$：

• 条件1：$u$ 或 $v$ 有发射器（直接覆盖）
• 条件2：$u$ 的邻居中有 ≥2 个发射器，或 $v$ 的邻居中有 ≥2 个发射器

条件2意味着：如果某个节点没有发射器，但它的两个邻居有发射器，那么与它相连的边也能被覆盖。

算法思路

树形动态规划

设 $dp[u][state]$ 表示以 $u$ 为根的子树所需的最小发射器数量，其中 $state$ 表示 $u$ 的状态和约束。

状态设计

对于每个节点 $u$，我们关心：

• $u$ 本身是否有发射器
• $u$ 的父节点是否有发射器
• $u$ 的覆盖状态

更精细的状态设计： 令 $dp[u][c]$ 表示节点 $u$ 的状态为 $c$ 时，子树 $u$ 的最小发射器数，其中 $c \in \{0,1,2,3\}$：

• 状态 0: $u$ 没有发射器，且 $u$ 未被覆盖（需要子节点或父节点提供覆盖）
• 状态 1: $u$ 没有发射器，但 $u$ 已被覆盖（邻居有发射器）
• 状态 2: $u$ 有 1 个发射器
• 状态 3: $u$ 有 ≥2 个发射器

状态转移

对于节点 $u$ 和其子节点 $v_1, v_2, ..., v_k$：

1. $u$ 状态 0（无发射器，未覆盖）：

   • 需要至少一个子节点状态为 2 或 3（提供覆盖）
   • 其他子节点可以是状态 1,2,3

2. $u$ 状态 1（无发射器，已覆盖）：

   • 需要至少两个子节点状态为 2 或 3，或者一个子节点状态为 3
   • 其他子节点可以是状态 1,2,3

3. $u$ 状态 2（1个发射器）：

   • 子节点可以是任意状态（因为 $u$ 的发射器能覆盖相邻边）

4. $u$ 状态 3（≥2个发射器）：

   • 子节点可以是任意状态

具体转移时，需要对子节点的状态组合进行背包DP。

复杂度分析

• 时间复杂度：$O(n)$，每个节点处理一次
• 空间复杂度：$O(n)$，存储DP状态

算法正确性

该DP状态设计考虑了所有覆盖情况：

• 状态0确保需要子节点提供覆盖
• 状态1确保满足"两个邻居有发射器"的条件
• 状态2和3直接提供覆盖能力

样例验证

样例1

输入：
7
1 2
2 3  
2 4
4 5
5 6
6 7
输出：2

验证：在节点2和6各放1个发射器，总数为2。

样例2

输入：
7  
1 2
2 3
4 3
5 4
6 3
7 6
输出：2

验证：在节点3放2个发射器，总数为2。

总结

本题是树形DP的经典应用，通过精细的状态设计处理复杂的覆盖条件。关键在于理解覆盖条件的本质并设计合适的状态表示。

最终算法标签： 树形DP 最小覆盖 状态压缩 DFS