题解 ARC116E【Spread of Information】

qfpjm · 2022-07-15 19:41:40 · 题解

题目大意

一个城市是由 n 个点 n-1 条边组成的树，一个点的危险度是指这个点到任意一个消防站的距离的最小值。现在要选择 k 个点建立消防站，使得所有点的危险度的最大值最小，求这个值。（1\leq k<n\leq 2\times 10^5）

题解

面对这样的数据规模，我们只能考虑 O(n),O(n\log n),O(n\sqrt{n}) 的做法，第三种不太可能，所以考虑前两种。看到"最大值最小"，我们就会想到二分，从而考虑第二种时间复杂度的做法。
二分，我们枚举什么？显然是 n，我们可以枚举每个消防站的覆盖范围，从而锁定答案。
这样，问题就转化成了一个树上半径为 k 最小覆盖问题。但是这题的 k 有些大，但是我们需要 O(n) 的时间复杂度。所以，需要做一些优化。
普通的树上半径为 k 最小覆盖问题，我们每次找到深度最大且没被覆盖的节点，并在其第 k 级祖先上设立消防站，这样可以证明是最优的。
这题我们还是考虑从下往上贪心，但我们从每个子树的根节点考虑。我们枚举到一个覆盖范围 mid，我们判断如果这颗子树的根节点 u，到这棵最深的节点 v 的距离为 mid，那么我们就在 u 上设立消防站，当然，意义同 k 很小的最小半径覆盖问题，但是并不是从下往上跳，而是由上考虑下。

实现方式：

我们用回溯思想，用儿子计算这颗子树的根的答案。我们用 a_u 表示u 离 u 这棵子树中的消防站的距离，b_u 表示 u 到 u 这棵子树中没被覆盖的点得距离。

如果 p\ge q，那么说明不能被覆盖的点可以被其它点覆盖，自然也能覆盖 u，所以我们更新 b_u=-1,a_u=p。
如果 q<mid，那么我们不覆盖节点 u，在该节点设立消防站不会使答案更优。更新 a_u=0,b_u=q。
否则，我们需要在 u 上设立消防站，更新 a_u=mid,b_u=-1，计数 num+1。

最后还要判断一下整棵树的根节点。
覆盖半径 mid 最终得到的答案 num 如果大于 k，那么说明这个覆盖半径太小了，需要调大；如果小于说明可以，但可能存在更优的半径，所以调小。

代码

#include <bits/stdc++.h>

using namespace std;

int n, k, ans, a[200005], b[200005], num, len;
vector<int> T[200005];

void dfs(int u, int fa)
{
    int p = -1, q = 0;
    for (int i = 0 ; i < T[u].size() ; i ++)
    {
        int v = T[u][i];
        if (v != fa)
        {
            dfs(v, u);
            p = max(p, a[v] - 1);
            q = max(q, b[v] + 1);
        }
    }
    if (p >= q)
    {
        a[u] = p;
        b[u] = -1;
        return ;
    }
    if (q < len)
    {
        a[u] = 0;
        b[u] = q;
        return ;
    }
    num ++;
    a[u] = len;
    b[u] = -1;
}

bool check(int x)
{
    memset(a, -1, sizeof(a));
    memset(b, -1, sizeof(b));
    len = x, num = 0;
    dfs(1, 0);
    if (b[1] != -1)
    {
        num ++;
    }
    if(num > k)
    {
        return 0;
    }
    return 1;
}

int main()
{
    cin >> n >> k;
    for (int i = 1 ; i < n ; i ++)
    {
        int u, v;
        cin >> u >> v;
        T[u].push_back(v);
        T[v].push_back(u);  
    }
    int l = 1, r = 200000;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (check(mid))
        {
            r = mid - 1;
            ans = mid;
        }
        else
        {
            l = mid + 1;
        }
    }
    cout << ans;
}