这是我写的第10？个正式题解
@AC君 修改题目标签为蓝色（个人认为是蓝下位）（黑色太过分了，而且洛谷上这题是青）
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
「HNOI2003」消防局的设立
题目链接
点这里
题目大意
定义 AAA 到 BBB 的距离为从 AAA 走到 BBB 最少经过的道路数量
要求设置若干消防站点，每个消防站点可以覆盖与其距离为 222 的所有节点
求覆盖所有节点所需最小消防站点数量
解题思路
1. 匹配算法
这题题目中有说到是“树状结构”，还要求求最小消防站点数量
所以是树形dp
2. 具体实现步骤
2.1 DP状态定义
因为我们发现与其距离为 222 相当于在树上覆盖了
* 爷爷
* 爸爸
* 自己
* 儿子
* 孙子
那么定义dp数组：
dp[i][0]dp[i][0]dp[i][0] 代表 iii 点放消防站，iii 的子树全覆盖，并且可以向上覆盖 iii 的父亲、iii 的祖父
dp[i][1]dp[i][1]dp[i][1] 代表 iii 的子树全覆盖，可以向上覆盖 iii 的父亲；iii 本身被儿子消防站覆盖
dp[i][2]dp[i][2]dp[i][2] 代表 iii 的子树全覆盖，i 本身被孙子消防站覆盖；向上没有覆盖能力
dp[i][3]dp[i][3]dp[i][3] 代表覆盖到 iii 的儿子最小消防站个数
dp[i][4]dp[i][4]dp[i][4] 代表覆盖到 iii 的孙子最小消防站个数
2.2 数学特征
基于状态定义，可以得到一条重要性质：dp[i][0]≥dp[i][1]≥dp[i][2]≥dp[i][3]≥dp[i][4]dp[i][0] \ge dp[i][1] \ge dp[i][2] \ge dp[i][3] \ge dp[i][4]dp[i][0]≥dp[i][1]≥dp[i][2]≥dp[i][3]≥dp[i][4]，整体单调不增。
背后逻辑：高配状态的所有可行方案，全部都是低配状态的合法方案。高配代表能力更强，它的整套布置方案，完全可以降级拿来满足低配的约束；也就是说低配的可行方案集合，包含高配的可行方案集合。
注意：该性质并不是转移计算完就天然成立。
我们的转移方程，只计算了恰好构造出当前状态的那一类方案，并不会自动把高配的方案纳入低配的候选当中。因此全部转移算完之后，必须手动做一轮维护：
这段代码的作用：从强能力状态向弱能力状态遍历，把高配状态的最优方案下放给低配状态。
维护完成之后，低配状态才拥有两类选择：要么使用自身原生构造出来的方案，要么直接复用高配已经算好的更优方案。
正是依靠维护得到的这条数学性质，我们在书写各个状态的转移时，只需要思考“恰好达成该状态”的构造方式，不需要额外叠加所有更强状态的情况。即使现实中有多种方案都可以满足本状态的约束，转移里也只写其中代表性的那一种；其余兼容情况统一交给这一轮后置 min 循环处理。
2.3 初始化
求最小值，所以dp= INFINFINF
但是对于叶子结点：
dp[i][0]=dp[i][1]=dp[i][2]=1dp[i][3]=dp[i][4]=0dp[i][0] = dp[i][1] = dp[i][2] = 1\\ dp[i][3] = dp[i][4] = 0 dp[i][0]=dp[i][1]=dp[i][2]=1dp[i][3]=dp[i][4]=0
为什么？因为 012 这三种状态都要由自身或者子节点考虑，但是 12 对于叶子结点不合法 ，所以全部设为 111
那 34 这两种状态会让未来的父亲或者祖父用，因此先置 000
2.4 状态转移
> 定义 s(x)s(x)s(x) 表示 xxx 节点的所有子节点
dp[i][0]=1+∑j∈s(i)dp[j][4]dp[i][0] = 1 + \sum_{j\in s(i)} dp[j][4] dp[i][0]=1+j∈s(i)∑ dp[j][4]
* 111：为了覆盖到 iii 的祖父，必须要在 iii 这里放一个节点
* ∑j∈s(i)dp[j][4]\sum_{j\in s(i)} dp[j][4]∑j∈s(i) dp[j][4]：因为 iii 的孩子 jjj 的孙子（也就是 iii 的曾孙）无法被 iii 覆盖到（因为距离为 333），所以需要加上每个孩子 jjj 的孙子的花费
累加即为 dp[i][0]dp[i][0]dp[i][0] 的代价
dp[i][1]=minj∈s(i)(dp[j][0]+∑k∈s(i)且k≠jdp[k][3])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[i][1]=j∈s(i)min dp[j][0]+k∈s(i)且k=j∑ dp[k][3]
* dp[j][0]dp[j][0]dp[j][0]：覆盖到 iii 的父亲，相当于覆盖到 jjj 的祖父，那么为了覆盖，代价为 jjj 覆盖其祖父的最小代价
* ∑k∈s(x)且k≠jdp[k][3]\sum_{k\in s(x)且k \neq j} dp[k][3]∑k∈s(x)且k=j dp[k][3]：因为对于 jjj 的所有兄弟的孩子，jjj 放点是覆盖不到的（因为距离为 333，j→i→k→⋯j\rightarrow i \rightarrow k \rightarrow \cdotsj→i→k→⋯），所以需要累加其他兄弟 kkk 使孩子覆盖到的代价
选择其中最小值，即为 dp[i][1]dp[i][1]dp[i][1] 的代价
dp[i][2]=minj∈s(i)(dp[j][1]+∑k∈s(i)且k≠jdp[k][2])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[i][2]=j∈s(i)min dp[j][1]+k∈s(i)且k=j∑ dp[k][2]
* dp[j][1]dp[j][1]dp[j][1]：为了覆盖到 iii，可以使用 iii 的孙子（jjj 的孩子覆盖）使得最小
* ∑k∈s(x)且k≠jdp[k][2]\sum_{k\in s(x)且k \neq j} dp[k][2]∑k∈s(x)且k=j dp[k][2]：因为对于 jjj 的所有兄弟，jjj 的孩子放消防站是覆盖不到的（因为距离为 333，j的孩子→j→i→kj的孩子 \rightarrow j \rightarrow i \rightarrow kj的孩子→j→i→k），所以需要这些孩子覆盖到自身
选择其中最小值，即为 dp[i][2]dp[i][2]dp[i][2] 的代价
dp[i][3]=∑j∈s(i)dp[j][2]dp[i][3] = \sum_{j\in s(i)} dp[j][2] dp[i][3]=j∈s(i)∑ dp[j][2]
* ∑j∈s(i)dp[j][2]\sum_{j\in s(i)} dp[j][2]∑j∈s(i) dp[j][2]：因为我们要使孩子那一层被覆盖，所以自然而然要让所有孩子 jjj 内部处理后覆盖到它们那一层（也就是我的下一层）
dp[i][4]=∑j∈s(i)dp[j][3]dp[i][4] = \sum_{j\in s(i)} dp[j][3] dp[i][4]=j∈s(i)∑ dp[j][3]
* ∑j∈s(i)dp[j][3]\sum_{j\in s(i)} dp[j][3]∑j∈s(i) dp[j][3]：和上面第四个转移差不多。因为我们要使孙子那一层被覆盖，所以自然而然要让所有孩子 jjj 的孩子（相当于我的孙子）处理后覆盖到它们那一层（也就是我的下下层）
2.5 答案求取
现在我们求完了，该取 dp[root(1)][0/1/2/3/4]dp[root(1)][0/1/2/3/4]dp[root(1)][0/1/2/3/4] 中的哪个呢？
答案是 dp[root(1)][2]dp[root(1)][2]dp[root(1)][2]
原因很简单：
我们是根节点，必须保证自己被覆盖（就代表其它已经全部被覆盖），否则可能会只使得根节点的孩子甚至根节点的孙子被覆盖，所以 3,43,43,4 要放弃
那么剩余的就是 dp[root(1)][0/1/2]dp[root(1)][0/1/2]dp[root(1)][0/1/2]，根据之前维护的单调性可以发现 dp[root(1)][0]≥dp[root(1)][1]≥dp[root(1)][2]dp[root(1)][0]\ge dp[root(1)][1] \ge dp[root(1)][2]dp[root(1)][0]≥dp[root(1)][1]≥dp[root(1)][2]，那么选择其中最小的自然就是 dp[root(1)][2]dp[root(1)][2]dp[root(1)][2]
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 优化（O(N2)→O(N)O(N^2)\RIGHTARROW O(N)O(N2)→O(N)）
这种代码的时间复杂度遇到菊花图的时候是 O(n2)O(n^2)O(n2)，虽然这道题能过，但是我们思考优化：
发现这里
使用了直白的双重循环，是代码的时间复杂度瓶颈 O(n2)O(n^2)O(n2)
但是可以先记录两个分别的sum，当遇到每一个点，考虑强行让其变成所需儿子的代价（比原来和改变谁大，改变代价大就是加上改变 −-− 原来的代价，原来代价大就是原来 −-− 改变的代价），其中最小值就是我们的答案
这样求和是 O(n)O(n)O(n)，枚举每一个子节点也是 O(n)O(n)O(n)，整体就是 O(n)O(n)O(n)
（代码不给，自己想优化）
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
有人可能说我这个咋和洛谷题解思路类似，我来告诉你：我是参考这位大佬的题解写的
但是代码和绝大多数表述都没有参考！
