这是我写的第10？个正式题解
@AC君 修改题目标签为蓝色（个人认为是蓝下位）（黑色太过分了，而且洛谷上这题是青）

---

「HNOI2003」消防局的设立

题目链接

点这里

题目大意

定义 $A$ 到 $B$ 的距离为从 $A$ 走到 $B$ 最少经过的道路数量
要求设置若干消防站点，每个消防站点可以覆盖与其距离为 $2$ 的所有节点
求覆盖所有节点所需最小消防站点数量

解题思路

1. 匹配算法

这题题目中有说到是“树状结构”，还要求求最小消防站点数量
所以是树形dp

2. 具体实现步骤

2.1 dp状态定义

因为我们发现与其距离为 $2$ 相当于在树上覆盖了

• 爷爷
• 爸爸
• 自己
• 儿子
• 孙子

那么定义dp数组：
$dp[i][0]$ 代表 $i$ 点放消防站，$i$ 的子树全覆盖，并且可以向上覆盖 $i$ 的父亲、$i$ 的祖父
$dp[i][1]$ 代表 $i$ 的子树全覆盖，可以向上覆盖 $i$ 的父亲；$i$ 本身被儿子消防站覆盖
$dp[i][2]$ 代表 $i$ 的子树全覆盖，i 本身被孙子消防站覆盖；向上没有覆盖能力
$dp[i][3]$ 代表覆盖到 $i$ 的儿子最小消防站个数
$dp[i][4]$ 代表覆盖到 $i$ 的孙子最小消防站个数

2.2 数学特征

基于状态定义，可以得到一条重要性质：$dp[i][0] \ge dp[i][1] \ge dp[i][2] \ge dp[i][3] \ge dp[i][4]$，整体单调不增。
背后逻辑：高配状态的所有可行方案，全部都是低配状态的合法方案。高配代表能力更强，它的整套布置方案，完全可以降级拿来满足低配的约束；也就是说低配的可行方案集合，包含高配的可行方案集合。
注意：该性质并不是转移计算完就天然成立。
我们的转移方程，只计算了恰好构造出当前状态的那一类方案，并不会自动把高配的方案纳入低配的候选当中。因此全部转移算完之后，必须手动做一轮维护：

for (int i = 1;i <= 4;i++){
    dp[u][i] = min(dp[u][i], dp[u][i - 1]);
}

这段代码的作用：从强能力状态向弱能力状态遍历，把高配状态的最优方案下放给低配状态。
维护完成之后，低配状态才拥有两类选择：要么使用自身原生构造出来的方案，要么直接复用高配已经算好的更优方案。
正是依靠维护得到的这条数学性质，我们在书写各个状态的转移时，只需要思考“恰好达成该状态”的构造方式，不需要额外叠加所有更强状态的情况。即使现实中有多种方案都可以满足本状态的约束，转移里也只写其中代表性的那一种；其余兼容情况统一交给这一轮后置 min 循环处理。

2.3 初始化

求最小值，所以dp= $INF$
但是对于叶子结点：

$$dp[i][0] = dp[i][1] = dp[i][2] = 1\\ dp[i][3] = dp[i][4] = 0$$

为什么？因为 012 这三种状态都要由自身或者子节点考虑，但是 12 对于叶子结点不合法 ，所以全部设为 $1$
那 34 这两种状态会让未来的父亲或者祖父用，因此先置 $0$

bool leaf = true;
for (int v : g[u]){
    if (v == fa) continue;
    leaf = false;
    dfs(v, u);
}
if (leaf){
    dp[u][2] = dp[u][1] = dp[u][0] = 1;
    dp[u][3] = dp[u][4] = 0;
    return ;
}

2.4 状态转移

定义 $s(x)$ 表示 $x$ 节点的所有子节点

$$dp[i][0] = 1 + \sum_{j\in s(i)} dp[j][4]$$

• $1$：为了覆盖到 $i$ 的祖父，必须要在 $i$ 这里放一个节点
• $\sum_{j\in s(i)} dp[j][4]$：因为 $i$ 的孩子 $j$ 的孙子（也就是 $i$ 的曾孙）无法被 $i$ 覆盖到（因为距离为 $3$），所以需要加上每个孩子 $j$ 的孙子的花费

累加即为 $dp[i][0]$ 的代价

$$dp[i][1] = \underset{j\in s(i)}{min}\left (dp[j][0]+\sum_{k\in s(i)且k \neq j} dp[k][3]\right)$$

• $dp[j][0]$：覆盖到 $i$ 的父亲，相当于覆盖到 $j$ 的祖父，那么为了覆盖，代价为 $j$ 覆盖其祖父的最小代价
• $\sum_{k\in s(x)且k \neq j} dp[k][3]$：因为对于 $j$ 的所有兄弟的孩子，$j$ 放点是覆盖不到的（因为距离为 $3$，$j\rightarrow i \rightarrow k \rightarrow \cdots$），所以需要累加其他兄弟 $k$ 使孩子覆盖到的代价

选择其中最小值，即为 $dp[i][1]$ 的代价

$$dp[i][2] = \underset{j\in s(i)}{min}\left (dp[j][1]+\sum_{k\in s(i)且k \neq j} dp[k][2]\right)$$

• $dp[j][1]$：为了覆盖到 $i$，可以使用 $i$ 的孙子（$j$ 的孩子覆盖）使得最小
• $\sum_{k\in s(x)且k \neq j} dp[k][2]$：因为对于 $j$ 的所有兄弟，$j$ 的孩子放消防站是覆盖不到的（因为距离为 $3$，$j的孩子 \rightarrow j \rightarrow i \rightarrow k$），所以需要这些孩子覆盖到自身

选择其中最小值，即为 $dp[i][2]$ 的代价

$$dp[i][3] = \sum_{j\in s(i)} dp[j][2]$$

• $\sum_{j\in s(i)} dp[j][2]$：因为我们要使孩子那一层被覆盖，所以自然而然要让所有孩子 $j$ 内部处理后覆盖到它们那一层（也就是我的下一层）

$$dp[i][4] = \sum_{j\in s(i)} dp[j][3]$$

• $\sum_{j\in s(i)} dp[j][3]$：和上面第四个转移差不多。因为我们要使孙子那一层被覆盖，所以自然而然要让所有孩子 $j$ 的孩子（相当于我的孙子）处理后覆盖到它们那一层（也就是我的下下层）

int sum = 0;
for (int v : g[u]){
    if (v == fa) continue;
    sum += dp[v][4];
}
dp[u][0] = 1 + sum;

for (int v : g[u]){
    if (v == fa) continue;
    sum = 0;
    for (int vv : g[u]){
        if (vv == fa || vv == v) continue;
        sum += dp[vv][3];
    }
    dp[u][1] = min(dp[u][1], dp[v][0] + sum);
}
    
for (int v : g[u]){
    if (v == fa) continue;
    sum = 0;
    for (int vv : g[u]){
        if (vv == fa || vv == v) continue;
        sum += dp[vv][2];
    }
    dp[u][2] = min(dp[u][2], dp[v][1] + sum);
}

sum = 0;
for (int v : g[u]){
    if (v == fa) continue;
    sum += dp[v][2];
}
dp[u][3] = sum;

sum = 0;
for (int v : g[u]){
    if (v == fa) continue;
    sum += dp[v][3];
}
dp[u][4] = sum;

2.5 答案求取

现在我们求完了，该取 $dp[root(1)][0/1/2/3/4]$ 中的哪个呢？
答案是 $dp[root(1)][2]$
原因很简单：
我们是根节点，必须保证自己被覆盖（就代表其它已经全部被覆盖），否则可能会只使得根节点的孩子甚至根节点的孙子被覆盖，所以 $3,4$ 要放弃
那么剩余的就是 $dp[root(1)][0/1/2]$，根据之前维护的单调性可以发现 $dp[root(1)][0]\ge dp[root(1)][1] \ge dp[root(1)][2]$，那么选择其中最小的自然就是 $dp[root(1)][2]$

---

3. 优化（$O(n^2)\rightarrow O(n)$）

这种代码的时间复杂度遇到菊花图的时候是 $O(n^2)$，虽然这道题能过，但是我们思考优化：
发现这里

for (int v : g[u]){
    if (v == fa) continue;
    sum = 0;
    for (int vv : g[u]){
        if (vv == fa || vv == v) continue;
        sum += dp[vv][3];
    }
    dp[u][1] = min(dp[u][1], dp[v][0] + sum);
}
    
for (int v : g[u]){
    if (v == fa) continue;
    sum = 0;
    for (int vv : g[u]){
        if (vv == fa || vv == v) continue;
        sum += dp[vv][2];
    }
    dp[u][2] = min(dp[u][2], dp[v][1] + sum);
}

使用了直白的双重循环，是代码的时间复杂度瓶颈 $O(n^2)$
但是可以先记录两个分别的sum，当遇到每一个点，考虑强行让其变成所需儿子的代价（比原来和改变谁大，改变代价大就是加上改变 $-$ 原来的代价，原来代价大就是原来 $-$ 改变的代价），其中最小值就是我们的答案
这样求和是 $O(n)$，枚举每一个子节点也是 $O(n)$，整体就是 $O(n)$
（代码不给，自己想优化）

---

有人可能说我这个咋和洛谷题解思路类似，我来告诉你：我是参考这位大佬的题解写的

但是代码和绝大多数表述都没有参考！