题解：P9983 [USACO23DEC] Cowntact Tracing P

· · 题解

令经过了 k 个夜晚。

考虑先预处理出所有可能的初始感染源，即到任意一个 0 的距离都 \gt k，跑一遍多源 BFS 即可。

如果存在一个点到最近初始感染源的距离 \gt k，那显然无解。

现在我们只需要在初始感染源集合中选取最少的点恰好覆盖所有为 1 的点。

我们将所有 1 按照深度从大到小排序处理，对于当前点 u，作为未被覆盖的最大深度的感染者，肯定会有一个初始感染源 s 来覆盖它。考虑如何最大化 s 的价值，即尽量覆盖多的 1。显然 s 应该越靠上，即深度越小越好，更有希望感染到上面的点，而 u 也能被感染。

考虑怎么快速查询这个东西。

我们预处理一个 f_u 表示 u 子树内部深度最小的初始感染源。当需要处理点 u 时，从 u 开始往上跳 k 步，查询所有遍历到的祖先 x 的 f_x，取 f_x 到 u 的距离 \le k 的深度最小的 f_x 当作 s 即可。

选定 s 之后，记一个 rem_x 表示点 u 的剩余覆盖距离，即还能往外感染多少距离。从 s 出发，向四周扩散，如果 rem_v \lt rem_u - 1 则将 v 入队。

这里给一下预处理 f 和查询的代码：

:::success[code]

vi f(n + 1, 0), seq(n); iota(seq.begin(), seq.end(), 1);
sort(seq.begin(), seq.end(), [](int a, int b){ return dep[a] > dep[b]; });
rep(u, seq){
    int s = vis[u] ? u : 0;
    rep(v, g[u]) if (v != fa[u]){
        int t = f[v];
        if (dep[t] < dep[s]) s = t;
    }
    f[u] = s;   
}
// L(i, 1, n) std::cout << f[i] << " \n"[i == n];
vi rem(n + 1, -1); int ans = 0;
rep(u, I){
    if (rem[u] >= 0) continue;
    int s = 0, x = u;
    for (rg int _ = 0; _ <= k && x != 0; _++){
        int v = f[x];
        if (dep[u] - dep[x] + dep[v] - dep[x] <= k && dep[v] < dep[s]) s = v;
        x = fa[x];
    }
    // std::cout << s << "\n";
    ans++, rem[s] = k, q.push(s);
    while(q.size()){
        int u = q.front(); q.pop(); if (!rem[u]) continue;
        rep(v, g[u]) if (rem[v] < rem[u] - 1) rem[v] = rem[u] - 1, q.push(v);
    }
}
std::cout << ans << "\n";

:::

考虑分析一下复杂度，首先预处理 f 有 \mathcal O(n \log n) 的排序，然后核心分析后面 BFS 那段。

首先每一个 rem_u 只在其变大时将 u 入队，而所有 rem_u 的上限为 k，所以总入队次数最多为 \mathcal O(nk) 次。

假设我们选择了 c 个初始感染源，由于每个初始感染源做一次 BFS 最多遍历 n 个点，所以总入队次数最多为 \mathcal O(nc) 次。

而一共最多只有 n 个点被感染，而每个初始感染源至少一次会感染 k 个点，所以一定有 c \times k \le n。

所以 \mathcal O(nk) 与 \mathcal O(nc) 的较小值一定小于等于 \mathcal O(n \sqrt n)。此时复杂度为 \mathcal O(n \sqrt n)。

故最坏时间复杂度为 \mathcal O(n \log n+qn \sqrt n)，约为 6 \times 10^8，常数比较小所以能过。