【Codeforces】1665C Tree Infection 题解

题目大意

给定一个 $n$ 节点的树，并且认定 $1$ 号节点为根。初始时，所有节点都是未感染状态，而我们的任务是感染这棵树。

每一秒中，我们依次执行以下两个操作：

• 如果一个节点 $v$ 的儿子节点中，至少有一个未感染，那么我们就可以至多再感染一个 $v$ 的儿子节点。
• 感染一个任意未被感染的节点。

输出最少需要多长时间感染所有节点。

题目链接

思路

观察发现，在同一个点的儿子节点是相互联系的，而与其它点没有任何关系。所以，把每个节点的儿子节点分为一组。

每一组都至少需要被感染一次，因为病毒会在被感染的组中每一秒都传染一个，所以为了使得所需时间最少，我们从数量最多的组开始感染。

每一组都感染完之后，若还有组没有被完全感染，那么我们就需要继续感染来加快进度。

而因为所有组都被感染了，每过一秒，感染数都会增加，所以我们不妨二分答案，设过 $x$ 秒后可以感染完，那么数量小于 $x$ 的组就不用感染了，我们有 $x$ 次机会去感染还没有被感染的节点。

最后不要忘了，根节点也需要单独感染一次，额外花了一秒钟时间。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

const int maxN = 2e5 + 7;

int T, n, son[maxN], cnt[maxN];

bool cmp(int x, int y)
{
    return x > y;
}

bool check(int x)
{
    int sum = 0;
    for(int i = 1; i <= cnt[0]; ++i) {
        if(cnt[i] > x)
            sum += cnt[i] - x;
        else
            break;
    }
    return sum <= x;
}

int main()
{
    scanf("%d", &T);
    while(T--) {
        memset(son, 0, sizeof son);
        cnt[0] = 0;
        scanf("%d", &n);
        for(int i = 1; i < n; ++i) {
            int x; scanf("%d", &x);
            son[x]++;
        }
        sort(son + 1, son + 1 + n, cmp);
        int mt = 0;
        while(son[n] == 0)
            n--;
        for(int i = 1; i <= n; ++i) {
            ++mt;
            son[i] -= (n - i + 1);
            if(son[i] > 1)
                cnt[++cnt[0]] = son[i] - 1;
        }
        if(cnt[0] == 0) 
            printf("%d\n", mt + 1);
        else {
            sort(cnt + 1, cnt + 1 + cnt[0], cmp);
            int sum = 0;
            for(int i = 1; i <= cnt[0]; ++i)
                sum += cnt[i];
            int l = 1, r = sum;
            while(l < r) {
                int mid = (l + r) >> 1;
                if(check(mid))
                    r = mid;
                else
                    l = mid + 1;
            }
            printf("%d\n", l + mt + 1);
        }
    }
    return 0;   
}