The content below was generated entirely by machine translation. Please verify its accuracy. If anything is unclear, consult the Chinese source version.

The reading experience is better on the blog.

1. Problem Statement:

You are given a tree with $n$ nodes. Initially, every node is healthy. Each second, you can perform the following two operations:

Spread: For a node, if at least one of its child nodes is infected, then another of its child nodes can be infected. (If multiple nodes satisfy the condition, multiple nodes can spread the infection during that second.)
Injection: You can choose any node in the tree and infect it. (Only one additional node can be infected in one second.)

Find the minimum number of seconds required to infect the entire tree.

2. Approach:

After reading the problem, we need to notice that it says a node can spread the virus to its siblings, rather than to its child nodes. Therefore, every level of the tree is completely independent, and it is impossible to spread the virus from one level to another.

Therefore, at the beginning, we certainly need to inject the virus into at least one child node of every node (which specific one does not matter), so that more nodes can be infected each second (according to operation 1).

Then whose child node should be injected first? Consider that child nodes injected earlier have more time to spread the virus to more child nodes. Therefore, we should first inject the nodes that have more child nodes.

(If we first inject a node with fewer child nodes, all of that node’s child nodes may already be infected before we finish injecting all nodes, meaning that a lot of time is wasted.)

After ensuring that every node has at least one injected child node, we can also inject the nodes with especially many child nodes, preventing some especially large nodes from being infected too slowly through spreading alone.

Of course, we cannot simply sort by the number of child nodes as before and continually inject the node with the most child nodes. Doing so might cause a node and its child nodes to become fully infected quickly while other nodes still require a long time.

For example, suppose two nodes have 100 and 98 healthy child nodes respectively after the injections. If we sort them directly and inject the larger node first, infecting the entire tree will still require $(100\div2) + \frac{(98 - (100\div2))}{2} = 74$ seconds. (The division by 2 is because spreading and injection infect nodes at the same time, while 98 minus 50 and then divided by 2 is because we only start injecting the node with 98 child nodes after finishing the node with 100.) However, if we inject both nodes concurrently, only $(100 + 98) \div 3 = 66$ seconds are needed. (The two nodes can be regarded as one node; each second, two child nodes are infected by spreading and one is infected by injection.)

Therefore, we can push the numbers of healthy child nodes into a heap and inject the one with the most child nodes each time.

3. Code:

I will not explain too much here; the code contains detailed comments.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;
int n;
int siz[MAXN], t;
// siz represents the number of child nodes of this node.

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;  // Connect node 0 to the root node, so node 0 has one child node.
        sort(siz, siz + 1 + n);
        int fir_n_zero = -1;  // The index of the first node whose number of child nodes is not 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++) {
            // In the loop, a node with a smaller i is injected later. You can understand i as the ith node from the end to be injected.
            pq.push(siz[i] - (i - fir_n_zero) - 1);
            // Inject one child node of every node once, but spreading also occurs during the injections. The number of child nodes infected by spreading is
            // i - fir_n_zero, while the number infected by injection is 1. Therefore, the number pushed
            // is the number of child nodes in each tree that remain uninfected after this round of injections.
        }

        int tm_used = n - fir_n_zero + 1; // The time used by this round of injections, which is the number of nodes that have child nodes.
        int spreaded = 0;

        while(pq.top() > spreaded){
            // Here, pq has not subtracted the number infected by spreading, because spreading occurs for every node.
            spreaded++;
            // One additional node is infected by spreading each time.
            int tp = pq.top();
            pq.pop();
            pq.push(tp - 1);
            // Choose the largest node for injection each time.
            tm_used++;
        }
        printf("%d\n", tm_used);
    }
}