题解：P11322 [NOISG 2020 Qualification] Firefighting

· · 题解

Statement

给定一棵树，边有边权。选出最少的关键节点建消防站，使得每个节点到最近的消防站的距离不大于 K。

Sol（greedy，dp）

注意到这道题就是有边权的，不用二分答案的，需要输出方案的 P3523。

具体地，我们有一个贪心思路，就是在能够满足子树中最深的节点能够被覆盖的情况下，将消防站建在尽量靠近根节点，也就是更浅的位置。

但是这样子暴力做是 O(n^2) 的，我们可以用 dp 进行优化。具体地，用 f_i 维护子树内最浅的消防站（若无，可以视作在无穷远处有一个消防站）的深度，g_i 维护子树内最深的坏节点（目前没有被消防站保护的节点）的深度。转移直接对儿子求 min/max 就可以。

如果我们发现最深的坏节点 g_i 可以被另一颗子树的消防站保护，那么子树 i 内所有的坏节点一定可以被保护。这是我们可以直接删除 g_i。

如果我们发现最深的坏节点 g_i 到达当前节点 i 的父亲的距离大于 K 了（或者 i 是根节点，但是仍然有坏节点没有被保护），我们就无法把保护这个坏节点的责任推给父亲，因此当前节点必须建立消防站。

如果这两种情况都没有发生，就什么都不做。

然后就做完了。

Code

#include<iostream>
#include<algorithm>
#include<vector>
#include<numeric>
using namespace std;
const int _= 3.1e5;
#define CMP(X) [&](int cu, int cv){return X;}
int n, ui, vi, fa[_];
long long dep[_], f[_], g[_], k, di; //警钟敲烂
vector<pair<int, int> > e[_];
vector<int> ans, ord;

void dfs(int o){
    for(auto eg : e[o]) if(eg.first != fa[o]){
        dep[eg.first] = dep[o] + eg.second;
        fa[eg.first] = o;
        dfs(eg.first);
    }
}

signed main(){
    ios::sync_with_stdio(0),
    cin.tie(0), cout.tie(0);
    cin >> n >> k;
    ord.resize(n), iota(ord.begin(), ord.end(), 1);
    for(int i = 1; i < n; i++){
        cin >> ui >> vi >> di;
        e[ui].push_back(make_pair(vi, di));
        e[vi].push_back(make_pair(ui, di));
    }
    dep[1] = 0, fa[1] = 1, dfs(1);
    sort(ord.begin(), ord.end(), CMP(dep[cu] > dep[cv]));
    for(int o: ord){
        f[o] = 2e18, g[o] = dep[o]; // 注意这里直接维护深度
        for(auto ex : e[o]) if(ex.first != fa[o]){
            if(f[ex.first] < f[o]) f[o] = f[ex.first];
            if(g[ex.first] > g[o]) g[o] = g[ex.first];
        }
        if(g[o] + f[o] - 2 * dep[o] <= k) g[o] = -1e17;
        else if(g[o] - dep[fa[o]] > k || (o == 1 && g[o] >= 0) ) 
            f[o] = dep[o], g[o] = -1e17, ans.push_back(o);
    }
    cout << ans.size() << endl;
    for(int&ax : ans){
        cout << ax << " ";
    }
}