博客中观看体验更佳

1.题意：

给你一个有 $n$ 个节点的树，一开始，每个节点都是健康的。每秒钟你可以进行下面两种操作：

传播：对于一个节点，如果它的至少一个子节点被感染了，那么可以感染它的另一个子节点。（如果有多个节点符合条件，那一秒钟就可以传播多个节点）
注射：你可以任选树中的一个节点进行感染。（一秒钟只能多感染一个节点）

现在问你最少需要多少秒才能感染整个树。

2.思路：

看完题我们要注意到，这个题说的是节点可以把病毒传播给他们的兄弟节点，而不是传播给他们的子节点，所以这个树的每一层之间是完全独立的，不可能把病毒从一层传播给另一层。

所以我们肯定需要在一开始的时候就给每个节点的至少一个子节点注射病毒（具体哪个不重要），这样每秒钟能感染的节点更多（根据操作 1）。

那先给谁的子节点注射呢？考虑先被注射的子节点会有更多的时间把病毒传播给更多的子节点。所以我们应该先给子节点更多的节点注射病毒。

（如果先给子节点少的节点注射，那在给所有节点注射完之前，这个节点的所有子节点可能都被感染了，也就是有很多时间被浪费了）。

在确保每个节点都有至少一个子节点被注射后，我们还可以给子节点特别多的那些节点注射病毒，防止有些特别大的节点靠传播来传染特别慢。

当然我们不能直接跟前面一样直接根据子节点数量来排序，并且一直给子节点多的节点注射病毒，因为这样可能会让某个节点以及它的子节点迅速的被完全感染，而其他的节点还需要很长时间。

比如有两个节点，他们在经过注射后的，健康的子节点的数量分别是 100 和 98，如果我们直接排序，先给大的节点注射，那感染完整个树就还需要 $(100\div2) + \frac{(98 - (100\div2))}{2} = 74$ 秒（/2是因为有传播和注射两种感染方式同时进行，而 98 - 50 之后再 /2 是因为我们先处理完 100 那个节点才去给 98 那个节点注射）。但是如果我们同时给两个节点注射，只需要 $(100 + 98) \div 3 = 66$ 秒的时间（因为可以把两个节点看成一个节点，那每秒就有两个子节点因为传播而感染，一个因为注射而感染）。

所以我们可以把健康的子节点数压入堆中，每次注射子节点最多的那个。

3.代码：

不过多解释，代码中有详细注释

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;
int n;
int siz[MAXN], t;
//siz 表示这个节点的子节点的数量

int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        memset(siz, 0, sizeof(siz));
        for (int i = 1; i < n; i++) {
            int fa;
            scanf("%d", &fa);
            siz[fa]++;
        }
        siz[0] = 1;  //让 0 号节点连到根节点，所以 0 号节点的子节点数量是 1
        sort(siz, siz + 1 + n);
        int fir_n_zero = -1;  //第一个子节点数量不是 0 的节点的下标

        fir_n_zero =
            find_if(siz, siz + 1 + n, [](int a) { return a != 0; }) - siz;

        priority_queue<int> pq;
        for (int i = fir_n_zero; i <= n; i++) {
            //循环中 i 小的节点是后被注射的，可以把 i 理解为倒数第 i 个被注射
            pq.push(siz[i] - (i - fir_n_zero) - 1);
            //给所有节点的某个子节点注射一遍，但是在注射的过程中还会传播，因为传播而被感染的子节点数就是
            // i - fir_n_zero，因为注射而被感染的是 1，所以被 push
            // 进去的数就是经过这一轮注射后，每个树还剩下几个子节点未被感染。
        }

        int tm_used = n - fir_n_zero + 1; //这一轮注射用掉的时间，也就是有子节点的节点的数量
        int spreaded = 0;

        while(pq.top() > spreaded){
            //这里的 pq 没有减去因为传播而感染的数量，因为每一个节点都会有传播
            spreaded++;
            //每次都会因为传播而多感染一个
            int tp = pq.top();
            pq.pop();
            pq.push(tp - 1);
            //每次挑选最大的节点注射
            tm_used++;
        }
        printf("%d\n", tm_used);
    }
}