题解：Cell Phone Network（P3659）

一、题目分析

本题要求在树上选择最少的节点建立信号塔，使得每个节点被自身或相邻节点覆盖，属于树的最小支配集问题。关键信息：

• 牧场构成一棵树（N个节点，N-1条边）
• 信号塔覆盖范围：自身及所有相邻节点
• 目标：最小化信号塔数量

二、解题思路

1. 问题建模：
   树的最小支配集（MDS）问题，使用树形动态规划求解。定义状态：

   • $dp[u][0]$：节点u未被覆盖，且子树已被支配的最小塔数
   • $dp[u][1]$：节点u建塔，子树已被支配的最小塔数
   • $dp[u][2]$：节点u未建塔但被覆盖，子树已被支配的最小塔数

2. 状态转移：
   通过后序遍历递归处理子树，根据子节点状态推导父节点状态。

3. 边界条件：
   叶子节点的状态需特殊处理，确保覆盖自身或父节点。

三、代码解析

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int Max = 1e5 + 10;

struct Edge {
    int to;
    int next;
} edge[Max];

int head[Max], tot;
int dp[Max][3];  // dp[u][0]:u未被覆盖；dp[u][1]:u建塔；dp[u][2]:u被覆盖但未建塔
int n;

// 添加无向边
void add(int u, int v) {
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}

// 树形DP核心函数
void dfs(int u, int pre) {
    dp[u][0] = 0;       // u未被覆盖，初始为0（但需子树覆盖）
    dp[u][1] = 1;       // u建塔，至少1个塔
    dp[u][2] = 0;       // u被覆盖，初始为0（需子树满足条件）
    int gap = inf;      // 记录子节点选与不选的最小差距

    bool ok = false;    // 标记是否有子节点建塔或被覆盖
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        if (v == pre) continue;  // 跳过父节点
        dfs(v, u);              // 递归处理子节点
        
        // 状态转移：u未被覆盖，需子节点被覆盖（建塔或被覆盖）
        dp[u][0] += min(dp[v][1], dp[v][2]);
        
        // u建塔，子节点可以是任意状态
        dp[u][1] += min(dp[v][0], min(dp[v][1], dp[v][2]));
        
        // u被覆盖但未建塔，子节点需满足：
        if (dp[v][2] < dp[v][1]) {
            // 子节点v被覆盖且未建塔更优
            dp[u][2] += dp[v][2];
            gap = min(gap, dp[v][1] - dp[v][2]);  // 记录选v与不选v的差距
        } else {
            // 子节点v建塔更优
            dp[u][2] += dp[v][1];
            ok = true;  // 子节点v建塔，u被覆盖
        }
    }
    // 若所有子节点都未建塔且未被覆盖，需强制选一个子节点
    if (!ok) {
        dp[u][2] += gap;
    }
}

int main() {
    ios::sync_with_stdio(false);
    while (cin >> n) {
        memset(head, -1, sizeof(head));
        tot = 0;
        for (int i = 1; i < n; i++) {
            int u, v;
            cin >> u >> v;
            add(u, v);
            add(v, u);
        }
        dfs(1, 0);  // 从根节点1开始DFS
        // 根节点没有父节点，取建塔或被覆盖的最小值
        cout << min(dp[1][1], dp[1][2]) << endl;
    }
    return 0;
}

四、状态转移解析

状态定义：

• $dp[u][0]$：u未被覆盖，要求所有子节点v必须被覆盖（建塔或被覆盖），即$dp[v][1]$或$dp[v][2]$的最小值之和。
• $dp[u][1]$：u建塔，子节点v可以是任意状态（未被覆盖、建塔、被覆盖），取最小值之和+1（u建塔的1个塔）。
• $dp[u][2]$：u被覆盖但未建塔，要求存在至少一个子节点v覆盖u（v建塔或v被覆盖且能覆盖u）。

五、示例解析

以样例输入为例：

5
1 3
5 2
4 3
3 5

树的结构如下：

    3
  / | \
1  4  5
      /
     2

1. DFS过程：

   • 叶子节点1、2、4的$dp[v][1]=1$，$dp[v][2]=inf$（无覆盖）。
   • 节点5的子节点为2和3：
     • $dp[5][1] = 1 + min(dp[2][*], dp[3][*])$
   • 节点3的子节点为1、4、5，综合计算后$dp[3][1]$和$dp[3][2]$的最小值为2。

2. 结果：
   根节点1的$min(dp[1][1], dp[1][2])=2$，即最少建2个信号塔。

六、注意事项

1. 无向边处理：
   使用邻接表存储无向边，DFS时通过$pre$参数避免回父节点。

2. 初始化：
   $head$数组初始化为-1，$dp[u][1]$初始化为1（建塔至少1个）。

七、复杂度分析

• 时间复杂度：O(N)，每个节点遍历一次，每条边处理一次。
• 空间复杂度：O(N)，存储邻接表和DP数组。

八、扩展思考

1. 树的最小支配集性质：
   对于树，最小支配集可通过树形DP在O(N)时间内求解，而一般图的MDS是NP难问题。

2. 状态优化：
   可进一步简化状态定义，如仅用$dp[u][0]$（u未建塔）和$dp[u][1]$（u建塔），但需更复杂的转移逻辑。

3. 多源支配集：
   若允许多个根节点，可通过类似方法处理，但本题固定根为1。