题解：P2279 [HNOI2003] 消防局的设立

jy_ua · 2026-02-26 18:04:42 · 题解

题解 P2279 【[HNOI2003] 消防局的设立】

题目这里

这是蒟蒻的第一篇题解嘿嘿。

这是一道经典的树形 DP 问题，尤其需要注意状态的定义。

首先简要概括一下，有一棵树，选取一些节点（消防站），这些节点能覆盖距离自身至多两个节点距离的节点，若树上的每一个节点都要求被覆盖，求这些节点的最小数量。

既然我们要求消防站的数量，我们就要知道每个点是否是消防站。

注意到我们可以由子树的状态来推导出该节点是否需要变成消防站，那么很明显这是一道树形 DP。

动态规划！

Step1. 状态设计

既然是 DP，我们首先得知道状态是什么。

正常逻辑来讲，我们想要知道需要多少消防站才能按顺序覆盖到一个节点，可以规定 f_{i} 表示第 i 个点被覆盖时所需要的消防站数量。

但这样我们无法转移非子节点的状态，可是非子节点也有可能会影响该节点的状态。

我们来观察一下，对于一个节点，我们最多覆盖往上 2 层和往下 2 层，我们完全可以分别设计这五个状态，如下：

对于每个点 x，有 5 个状态，用 f_{x,j} 表示，其中 j \in \{-2,-1,0,1,2\}：

根据定义，我们不难发现这些状态之间存在包含关系：一个能覆盖到更高层的方案，必然也能满足较低层的覆盖要求。因此，对于同一个 x，这五个状态的值有如下大小关系：

f_{x,2} \ge f_{x,1} \ge f_{x,0} \ge f_{x,-1} \ge f_{x,-2}

这个关系会在最后一步用来更新最优解。

很好！至此，我们如果要转移一个点的状态，完全可以用第二个状态 j 来表示他们的关系。

既然我们已经能让这个 DP 状态具备转移的条件了，开始转移方程。

Step2. 状态转移方程

在此之前，我们先设 \text{son}(x) 表示 x 的儿子集合。然后开始吧！

方程一：

f_{x,2} = 1 + \sum_{y \in \text{son}(x)} f_{y,-2}

让我们细品一下……

首先，对于节点 x，如果 x 向上 2 层（祖父层）能被覆盖的话，由于我们是从 x 往其祖先节点转移状态的，那么 x 一定是消防站，才能让祖父层被覆盖。我们要给答案加一。
其次，我们发现，对于 x 的儿子 y，y 的孙子并不能被覆盖，因为 x 到这个曾孙节点的距离为 3，覆盖不到。所以，我们必须处理这个点。对于所有这样的点，我们要额外统计覆盖它所需的消防站数量。
因此，f_{x,2} 就等于加上曾孙节点所需的消防站的数量之和加上自身所需的一个。

方程二：

f_{x,1} = \min_{y \in \text{son}(x)} \left( f_{y,2} + \sum_{\substack{z \in \text{son}(x) \\ z \neq y}} f_{z,-1} \right)

有点可怕…但其实也是由两部分组成的。

现在我们要覆盖 x 点向上 1 层的点，由于我们已经有了子孙节点向上 2 层的答案了，这个时候，我们可以选取一位儿子 y，来担任这个伟大的任务（变成消防站）。
要找到这个最合适的 y，我们就要知道选取每一个 y 会产生怎样的贡献。注意到 y 产生的贡献，分为两部分。
第一部分，是它覆盖到我们要求的 x 的向上 1 层所需要的值。显然，这个数量是 f_{y, 2}。
第二部分，由于 x 的其他子孙节点可能无法覆盖到，我们需要统计这些节点所需的消防站数量。对于一个其他子节点 z，它本身能被 y 覆盖（距离为 2），但它的儿子无法被覆盖，因此需要由这个儿子的子树的消防站来覆盖，取 f_{z,-1}，求和即可。
我们得到一个 y 的贡献后，取所有 y 的贡献最小值，就是 f_{x,1} 的最小值了。

方程三：

f_{x,0} = \min_{y \in \text{son}(x)} \left( f_{y,1} + \sum_{\substack{z \in \text{son}(x) \\ z \neq y}} f_{z,0} \right)

好熟悉的公式，显然，这和方程二是同一个推理逻辑，这里简要概述：

假设有消防站为一个子节点 y 的儿子，则可以刚好覆盖到我们要求的 x 本层，那么现在我们求 y 的贡献（这里注意，树形 DP 中一个节点的状态一定是由子节点转移来的，这里虽然 y 的儿子为消防站，但我们依然求 y 的贡献）。
第一部分，x 的同一层是 y 的上 1 层，故要覆盖这一层，取值 f_{y,1}。
第二部分，对于异于 y 的子节点 z，z 已经不能被覆盖，故额外取 f_{z,0}。

方程四：

f_{x,-1} = \sum_{y \in \text{son}(x)} f_{y,0}

现在上下两层内已经没有消防站了，我们需要改变决策。

好在我们前面已经处理完了祖先及本节点 x 的情况，我们无需再关心 x 和它的祖先们是否被覆盖了。

因此，我们直接由子树的状态转移而来。

我们发现 x 的下一层是子节点的同一层，所以 f_{x,-1} 为儿子们的贡献之和。

由此我们可以得到方程四。

方程五：

f_{x,-2} = \sum_{y \in \text{son}(x)} f_{y,-1}

最简单的一集，不过多介绍，同方程四。因为要覆盖到孙子层，可以由儿子的儿子的覆盖方案处理。

注意

根据我们一开始推导状态定义时的包含关系：

f_{x,2} \ge f_{x,1} \ge f_{x,0} \ge f_{x,-1} \ge f_{x,-2}

我们还要额外取最小值！如：

    // 下一层可以用本层的方案，需要取最优
    for (int i = 3; i >= 0; i--)
        dp[u][i] = min(dp[u][i], dp[u][i + 1]);

（注意这里数组的第二维索引 i 与递推式中 j 要转换一下，即 i = j + 2，不能用负数的 j 直接当索引）。

Step3. 边界条件

啊！我们还没有设定 f_{i,j} 的初始值呢，这样肯定不行。

前面说过，树形 DP 中一个节点的状态一定是由子节点转移来的。那么我们可以设定叶子节点的状态，这是因为叶子节点不能被转移得来。这样对于叶子节点 x 我们有：

\begin{cases} f_{x,2} = f_{x,1} = f_{x,0} = 1 \\ f_{x,-1} = f_{x,-2} = 0 \end{cases}

为什么呢，我们不妨从题目的规则入手。

显然，如果叶子节点要去覆盖自己的上 2 层和本层节点，必然自身要设为消防站，即为 1。
其次，由于叶子节点没有儿子，所以无须覆盖下层节点，即为 0。

Step4. 最终答案

我们以 1 号节点为根，那么最终目标为 f_{1,0}。

Step5. 复杂度计算

让我们看看时间复杂度：

时间复杂度：O(n^2)。

空间复杂度：O(n)。

均已过关~ 迎接 AC！

展示代码！

// P2279 [HNOI2003] 消防局的设立
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

const int MAXN = 1005;

int n;
int dp[MAXN][5];
// dp[u][0] : 覆盖到孙子层（-2）
// dp[u][1] : 覆盖到儿子层（-1）
// dp[u][2] : 覆盖到本层（0）
// dp[u][3] : 覆盖到父层（1）
// dp[u][4] : 覆盖到祖父层（2）
vector<int> e[MAXN]; // 邻接表

void DFS(int u, int fa)
{
    // 叶子节点判断
    bool isLeaf = true;
    for (int v : e[u])
    {
        if (v == fa)
            continue;
        isLeaf = false;
        DFS(v, u);
    }
    // 叶子节点初始化
    if (isLeaf)
    {
        dp[u][2] = dp[u][3] = dp[u][4] = 1;
        dp[u][0] = dp[u][1] = 0;
        return;
    }
    // ===== 方程1：dp[u][4] =====
    int sum = 0;
    for (int v : e[u])
    {
        if (v == fa)
            continue;
        sum += dp[v][0];
    }
    dp[u][4] = 1 + sum;
    // ===== 方程2：dp[u][3] =====
    for (int v : e[u])
    {
        if (v == fa)
            continue;
        sum = 0;
        for (int s : e[u])
        {
            if (s == fa || s == v)
                continue;
            sum += dp[s][1];
        }
        dp[u][3] = min(dp[u][3], dp[v][4] + sum);
    }
    // ===== 方程3：dp[u][2] =====
    for (int v : e[u])
    {
        if (v == fa)
            continue;
        sum = 0;
        for (int s : e[u])
        {
            if (s == fa || s == v)
                continue;
            sum += dp[s][2];
        }
        dp[u][2] = min(dp[u][2], dp[v][3] + sum);
    }
    // ===== 方程4：dp[u][1] =====
    sum = 0;
    for (int v : e[u])
    {
        if (v == fa)
            continue;
        sum += dp[v][2];
    }
    dp[u][1] = sum;
    // ===== 方程5：dp[u][0] =====
    sum = 0;
    for (int v : e[u])
    {
        if (v == fa)
            continue;
        sum += dp[v][1];
    }
    dp[u][0] = sum;
    // 下层可以用本层的方案，需要取最优
    for (int i = 3; i >= 0; i--)
        dp[u][i] = min (dp[u][i], dp[u][i + 1]);
}

int main()
{
    // Input
    cin >> n;
    for (int i = 2; i <= n; i++)
    {
        int a;
        cin >> a;
        e[a].push_back(i);
        e[i].push_back(a);
    }
    // Main
    memset(dp, 0x3f, sizeof(dp));
    DFS(1, 0);
    // Output
    cout << dp[1][2] << endl;
    return 0;
}