题解：P11322 [NOISG 2020 Qualification] Firefighting

zgmbsydmz · 2026-11-07 11:14:01 · 题解

:::warning[说明] 本题解使用了 AI 美化格式，保证本人贡献不小于 AI。 :::

可能的更好的阅读体验

题意简述

给定一棵 n 个节点的带权树，边权为正整数。可以选取一些节点建立消防站，每个消防站能覆盖与其距离不超过 k 的所有节点。求覆盖整棵树所需的最少消防站数量及一种方案。

解题思路

本题与 P3942 将军令 十分相似，考虑在简单贪心的基础上进行修改。

贪心思路：按节点深度从深到浅遍历。若当前节点尚未被覆盖，则选取能覆盖到当前节点的最浅被选节点。

:::success[正确性证明] 若当前节点未被覆盖，自然需要选一个节点覆盖它。

为了找到这个最浅被选节点，需要从当前节点出发沿着父亲向上跳，这个过程可以用倍增实现。

于是写出了初步代码，加入剪枝后提交，发现 TLE。

为什么会 TLE

初步代码中暴力模拟了选点后的覆盖过程，遍历标准是“节点可以被覆盖”。虽然加入了剪枝优化，但复杂度依然可以被卡到 O(n^2)，因为无法保证每个节点只被覆盖一次。

:::info[关于剪枝优化] 记录覆盖到当前节点的历史最远可覆盖距离。若本次覆盖到当前节点时该距离小于等于历史值，则本次可覆盖的节点在以前的覆盖中已经被覆盖过了，直接跳过。

加入这个剪枝后可以通过 P3942，但在本题会 TLE：记录的结果可能被更新很多次，导致节点被反复覆盖。

正确的优化：DP 优化贪心

贪心本身没有问题，只要保证每个节点只被覆盖一次即可通过。因此使用 DP 优化贪心。

维护每个节点子树内：

• 最深未覆盖节点的深度；
• 最浅被选节点的深度。

转移时对所有儿子取 \min / \max。由于保留了按深度从大到小的处理顺序，处理当前节点时其所有儿子一定已经处理完毕。

这部分 @Error_Eric 大佬的题解已详细说明，此处不再展开。

若当前子树中最深未覆盖节点可以被最浅被选节点覆盖，说明当前子树已经全部被覆盖，不存在未覆盖节点。此时将最深未覆盖节点设为极小值，表示“不存在未覆盖节点”，并保留最浅被选节点。

若上述条件不成立，则尝试把问题推给父亲：若父亲到最深未覆盖节点的距离已经超过 k，或者当前节点没有父亲（即根节点），说明不能再拖，必须在当前节点建立消防站，并更新两个 DP 值。

上面两段不理解也没关系，下面是更详细的解释。

DP 优化的原理与正确性

本篇题解侧重以萌新便于理解的角度解释这一部分，严谨性可能略有缺失，请各位大佬见谅。

解释 DP 过程及可能产生的疑问。

如果当前子树中最深的未覆盖节点可以被最浅被选节点覆盖，那么当前子树已经全部被覆盖。

如果最浅被选节点都能覆盖到最深未覆盖节点，那么其余所有未覆盖节点一定也能被某个被选节点覆盖。

:::info[会不会存在一个较深的被选节点可以覆盖最深未覆盖节点，但最浅被选节点无法做到？] 不会。

如果这个较深被选节点与未覆盖节点相对于当前处理节点在同一子树内，那么在处理它们的最近公共祖先时，这个未覆盖节点就已经被覆盖掉了。

不存在未覆盖节点，所以设为极小值表示不存在未覆盖节点，并保留最浅被选节点。

显然成立，不再解释。

如果上面这条不成立，就尝试把问题推给当前节点的父亲。

这是优化的关键：把原本在第一个未覆盖节点处新建消防站的操作，推迟到了被选节点的位置。

• 对于在该节点之前遍历的节点，其覆盖操作被推迟，因此这些节点只遍历一次。
• 对于在该节点之后遍历的节点，更新时会使用维护的最浅被选节点，因此也只遍历一次。

可以理解为：每个节点的覆盖操作从“每有一个可将其覆盖的节点就更新”改为“每个节点仅在被遍历时更新一次”。

如果当前节点的父亲距离最深未覆盖节点的距离已经超过 k，或者当前节点没有父节点，则不能再拖，选择当前节点，并更新两个 DP 值。

当前维护的最深未覆盖节点是“已经拖到最久”的未覆盖节点。当它到父亲的距离超过 k 时，无论再选哪个祖先都无法覆盖它，因此必须在当前节点建站（当前节点到它的距离不会超过 k）。

没有父节点对应根节点。根节点是深度最小的节点，也是遍历的最后一个节点，后面没有任何节点可以帮忙覆盖，因此必须在这里解决所有遗留的未覆盖节点。

:::info[会不会有遗漏的节点？] 不会。

具体实现与代码

DFS 求出每个节点的深度。将节点按深度从大到小排序，依次处理：

1. 用儿子信息更新当前节点的最浅被选节点与最深未覆盖节点；
2. 判断最深未覆盖节点能否被当前子树内最浅被选节点覆盖。若能，则清空最深未覆盖节点；
3. 否则判断是否需要把问题推给父亲。若不能推，则在当前节点建站；
4. 最后遍历所有节点，输出被标记为消防站的节点。

:::info[AC 代码（使用了 AI 用于格式化码风）]{open}

#include<queue>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

#define ll long long

const int N = 3e5 + 5;

int n, ans, idx = -1, idy;// idy 是重排数据时使用的下标
ll k;

int head[N], nex[N * 2], val[N * 2], wei[N * 2];// 链式前向星建图，wei 为边权

struct node {
    int fa, id, vis;// 父亲节点，节点原编号，节点是否被选择
    ll dep, g, f;// 节点深度，g、f 为 dp 优化，含义见上文
} a[N];// 存储每个点信息

node qu[N];

ll in() {// 快读，不解释
    ll num = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        num = num * 10 + (c - '0');
        c = getchar();
    }
    return num * f;
}

void out(ll x) {// 快写
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x < 10) putchar(x + '0');
    else {
        out(x / 10);
        putchar(x % 10 + '0');
    }
}

void add(int u, int v, int q) {// 链式前向星加边
    val[++idx] = v;
    nex[idx] = head[u];
    wei[idx] = q;
    head[u] = idx;
}

bool cmp(node a, node b) {// 按深度从大到小排序
    return a.dep > b.dep;
}

void dfs(int now) {// dfs 求深度
    qu[++idy] = a[now];
    for (int i = head[now]; ~i; i = nex[i]) {
        int v = val[i];
        if (v == a[now].fa) continue;
        a[v].dep = a[now].dep + wei[i];
        a[v].fa = now;
        dfs(v);
    }
}

int main() {
    memset(head, -1, sizeof(head));

    n = in();
    k = in();

    for (int i = 1; i < n; i++) {
        int u, v, w;
        u = in(); v = in(); w = in();
        add(u, v, w);
        add(v, u, w);
        a[i + 1].id = i + 1;
    }

    a[1].id = 1;
    dfs(1);

    sort(qu + 1, qu + idy + 1, cmp);// 按深度从大到小排序（贪心）

    for (int i = 1; i <= idy; i++) {
        int now = qu[i].id;

        a[now].f = (ll)2e18;// dp 初始化
        a[now].g = a[now].dep;

        for (int j = head[now]; ~j; j = nex[j]) {// 状态转移
            int v = val[j];
            if (v == a[now].fa) continue;
            a[now].f = min(a[now].f, a[v].f);
            a[now].g = max(a[now].g, a[v].g);
        }

        if (a[now].g + a[now].f - 2 * a[now].dep <= k) {// 最深坏点深度 + 最浅被选节点深度 - 2 * 当前节点深度 <= k
            a[now].g = (ll)-2e18;
        } else if (a[now].g - a[a[now].fa].dep > k || (now == 1 && a[now].g >= 0)) {// 最深坏点到父亲的距离超过 k，或根节点仍有未覆盖节点
            // 不能再往父亲拖了，在当前节点建立消防站
            a[now].f = a[now].dep;
            a[now].g = (ll)-2e18;
            a[now].vis = 1;
            ans++;
        }
    }

    out(ans);
    printf("\n");
    for (int i = 1; i <= n; i++) {
        if (a[i].vis) {
            out(i);
            putchar(' ');
        }
    }
    cout << endl;

    return 0;
}

:::

AC 记录

学会了就点个赞再走吧 QAQ，写了好久的题解……