这是我写的第10？个正式题解

---

「HNOI2003」消防局的设立

题目链接

点这里

题目大意

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

解题思路

1. 匹配算法

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

2. 具体实现步骤

2.1 dp状态定义

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

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

那么定义dp数组：
$dp[i][0]$ 代表 $i$ 这个位置放消防站，$i$ 的爷爷以及以 $i$ 为根节点的整棵子树全被覆盖的最少消防站点数量
$dp[i][1]$ 代表 $i$ 这个位置不放消防站（$i$ 的儿子放消防站），$i$ 的父亲以及以 $i$ 为根节点的整棵子树全被覆盖的最少消防站点数量
$dp[i][2]$ 代表 $i$ 这个位置不放消防站（$i$ 的孙子放消防站），以 $i$ 为根节点的整棵子树全被覆盖的最少消防站点数量
$dp[i][3]$ 代表以 $i$ 的孩子为根节点的整棵子树全被覆盖的最少消防站点数量
$dp[i][4]$ 代表以 $i$ 的孙子为根节点的整棵子树全被覆盖的最少消防站点数量

2.2 数学特征

经过定义，抛出一个概念：$dp[i][0] \le dp[i][1] \le dp[i][2] \le dp[i][3] \le dp[i][4]$
为什么，因为我们可以发现越是偏向 $dp[i][4]$ 的那些状态，包含的范围就越小，则所需消防站点的数量一定是单调不减的

AC 代码

#include <bits/stdc++.h>
using namespace std;

int n;
const int N = 1111;
vector<int> g[N];
int dp[N][5];
void dfs(int u, int fa){
    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 ;
    }
    //
    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;
    //
    for (int i = 1;i <= 4;i++){
        dp[u][i] = min(dp[u][i], dp[u][i - 1]);
    }
}

int main(){

    cin >> n;
    if (n == 1){
        cout << 1;
        return 0;
    }
    for (int i = 2;i <= n;i++){
        int a;
        cin >> a;
        g[i].push_back(a);
        g[a].push_back(i);
    }
    memset(dp, 0x3f, sizeof(dp));
    dfs(1, -1);
    cout << dp[1][2];
    
    return 0;
}
// 不是这题洛谷上青为啥这里是黑