题解 P2279 【[HNOI2003]消防局的设立】
rickole
2019-05-10 08:48:44
……蒟蒻第一次写题解，理解深入程度可能欠佳，望海涵。qwq
这是个树形dp。那首先……状态表示是：
F[i][state]表示节点i在state状态下的最小消防站个数
### 状态设计
然而，怎么设计状态呢……我直接在这一步卡住了，看了很多题解也没太明白。各位巨神题解的做法里都设了5个状态，但它们看起来毫无关联啊……极弱的我盯着看了半天，迷惑地问道：“这都是咋想到的啊？？？为啥有5个状态啊？为啥是这5个啊？”
想了一段时间之后，我似乎发现，这5个状态其实是有内在联系的。按我的理解，我把这些状态定义为：
```latex
F[i][0]表示可以覆盖到从节点i向上2层的最小消防站个数
F[i][1]表示可以覆盖到从节点i向上1层的最小消防站个数
F[i][2]表示可以覆盖到从节点i向上0层的最小消防站个数
F[i][3]表示可以覆盖到从节点i向上-1层的最小消防站个数
F[i][4]表示可以覆盖到从节点i向上-2层的最小消防站个数
```
其中，“覆盖到某层”的意思是在这棵子树中这一层和其以下层的所有点都被消防站覆盖到。比如，
“覆盖到从节点i向上1层”指的是“以节点i为根的整棵子树和i的父亲都被覆盖”，
“覆盖到从节点i向上-1层”指的是“节点i的所有儿子和它们的子孙都被覆盖”。
所以这就可以解释为什么是这5个状态了……为什么没有“覆盖到从节点i向上3层”？因为不可能。为什么没有“覆盖到从节点i向上-3层”？因为这是必须的。如果在这时候都没有覆盖全i的孙子，再向上递推时也就不可能覆盖它们了，所以设出这个状态没有意义。
哦对了，还有，在这五个状态中，上面的状态是包含下面的状态的。比如，如果能覆盖到节点i向上2层，则一定能覆盖到节点i向上1层。所以，有
$F[i][0]\ge F[i][1]\ge F[i][2]\ge F[i][3]\ge F[i][4]$
### 状态转移
$F[i][0] = 1+\displaystyle\sum_{\text{s是i的儿子}} F[s][4]$
因为i可以覆盖到向上2层，所以它自己必须是消防站。此时，它可以覆盖到所有儿子和孙子，因此儿子的状态可以是F[s][0~4]中的任意一种情况。但因为我们需要使得消防站个数最少，所以取F[s][4]。
$F[i][1] = \displaystyle\min_{\text{s是i的儿子}}\{{ F[s][0] + \sum_{\text{t是i的儿子,}t\ne s}{F[t][3]}} \}\quad \text{和}F[i][0]\text{中的最小值}$
因为i可以覆盖到向上1层，所以存在两种情况：要么恰好覆盖到i上面的1层，要么向上覆盖2层。
如果恰好覆盖到向上1层，那么i的至少一个儿子必须是消防站。其它儿子的状态可以是F[t][0~3]中的任意一种。同样，因为要取消防站个数最小值，取F[t][3]。
而如果向上覆盖两层，情况和F[i][0]是一样的。
取这两者最小值。
$F[i][2] =\displaystyle \min_{\text{s是i的儿子}}\{{ F[s][1] + \sum_{\text{t是i的儿子,}t\ne s}{F[t][2]}}\}\quad \text{和}F[i][0\text{-}1]\text{中的最小值}$
因为i可以覆盖到向上0层，所以要么恰好向上覆盖0层，要么向上覆盖1~2层。
如果向上覆盖0层，那么i的至少一个孙子必须是消防站，其它儿子的状态可以是F[t][0~2]中的任意一种。取F[t][2]。
而如果向上覆盖两层，情况和F[i][0]和F[i][1]是一样的。
取这三者最小值。
$F[i][3] =\displaystyle \sum_{\text{s是i的儿子}}\{F[s][2]\}\quad \text{和}F[i][0\text{-}2]\text{中的最小值}$
如果i恰好可以覆盖到向上-1层，即所有儿子被覆盖就可以。于是取F[s][2]。其它情况和上面取最小值。
$F[i][4] =\displaystyle \sum_{\text{s是i的儿子}}\{F[s][3]\}\quad \text{和}F[i][0\text{-}3]\text{中的最小值}$
如果i恰好可以覆盖到向上-2层，即所有孙子被覆盖就可以。取F[s][3]。其它情况和上面取最小值。
于是……就这样啦。
### 最终目标
我们希望寻找当整棵树都被覆盖的时候的消防站最小值，于是需要覆盖到根的这一层，于是结果是F[1][2]。
### 代码
```cpp
#include<iostream>
#include<algorithm>
using namespace std;
#define maxN 1010
#define INF 2000000000
int N;
struct edge{
int to;
int next;
}sons[maxN]; //前向星存图
int head[maxN] = {0}; //前向星存图
int F[maxN][5];
int nowEdge = 0;
void addSon(int u, int v){
nowEdge++;
sons[nowEdge].to = v;
sons[nowEdge].next = head[u];
head[u] = nowEdge;
}
void dfs(int now){
F[now][0] = 1;
F[now][3] = 0;
F[now][4] = 0;
for(int i = head[now]; i; i = sons[i].next){
int s = sons[i].to;
dfs(s);
F[now][0] += F[s][4];
F[now][3] += F[s][2];
F[now][4] += F[s][3];
}
if(head[now] == 0){
F[now][1] = F[now][2] = 1;
//特殊情况：如果now没有儿子，特殊处理
}
else{
F[now][1] = F[now][2] = INF;
for(int i = head[now]; i; i = sons[i].next){
int s = sons[i].to;
int F1 = F[s][0];
int F2 = F[s][1];
for(int j = head[now]; j; j = sons[j].next){
if(i == j) continue;
int t = sons[j].to;
F1 += F[t][3];
F2 += F[t][2];
}
F[now][1] = min(F[now][1], F1);
F[now][2] = min(F[now][2], F2);
}
}
for(int i = 1; i <= 4; i++){
F[now][i] = min(F[now][i], F[now][i-1]);
//把F[now][i]和前面取最小值的工作放在这里统一进行
}
}
int main(){
cin >> N;
for(int i = 2; i <= N; i++){
int f;
cin >> f;
addSon(f, i);
}
dfs(1);
cout << F[1][2];
}
```
Qwq