Programming Competition
Contest: Codeforces Round 916 (Div. 3)
Difficulty rating: 1900
Tags: dfs and similar, dp, graph matchings, greedy, trees

BerSoft is the biggest IT corporation in Berland. There are $$$n$$$ employees at BerSoft company, numbered from $$$1$$$ to $$$n$$$.

The first employee is the head of the company, and he does not have any superiors. Every other employee $$$i$$$ has exactly one direct superior $$$p_i$$$.

Employee $$$x$$$ is considered to be a superior (direct or indirect) of employee $$$y$$$ if one of the following conditions holds:

- employee $$$x$$$ is the direct superior of employee $$$y$$$;
- employee $$$x$$$ is a superior of the direct superior of employee $$$y$$$.

The structure of BerSoft is organized in such a way that the head of the company is superior of every employee.

A programming competition is going to be held soon. Two-person teams should be created for this purpose. However, if one employee in a team is the superior of another, they are uncomfortable together. So, teams of two people should be created so that no one is the superior of the other. Note that no employee can participate in more than one team.

Your task is to calculate the maximum possible number of teams according to the aforementioned rules.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of employees.

The second line contains $$$n-1$$$ integers $$$p_2, p_3, \dots, p_n$$$ ($$$1 \le p_i \le n$$$), where $$$p_i$$$ is the index of the direct superior of the $$$i$$$-th employee.

The sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, print a single integer — the maximum possible number of teams according to the aforementioned rules.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, team $$$(3, 4)$$$ can be created.

In the second test case, no team can be created, because there are only $$$2$$$ employees and one is the superior of another.

In the third test case, team $$$(2, 3)$$$ can be created.

In the fourth test case, teams $$$(2, 4)$$$, $$$(3, 5)$$$ and $$$(6, 7)$$$ can be created.

In the fifth test case, teams $$$(2, 3)$$$, $$$(6, 4)$$$ and $$$(5, 7)$$$ can be created.

Example input:
6
4
1 2 1
2
1
5
5 5 5 1
7
1 2 1 1 3 3
7
1 1 3 2 2 4
7
1 2 1 1 1 3

Example output:
1
0
1
3
3
3

Editorial:
Note that the problem basically states the following: you are given a rooted tree; you can pair two vertices $$$x$$$ and $$$y$$$ if neither $$$x$$$ is an ancestor of $$$y$$$ nor $$$y$$$ is an ancestor of $$$x$$$. Each vertex can be used in at most one pair. Calculate the maximum possible number of pairs you can make.
Let's look at subtrees of child nodes of the root. If two vertices belong to different subtrees, we can pair them up. So we can slightly rephrase the problem: given $$$m$$$ types of objects, with counts $$$sz_1, sz_2, \dots, sz_m$$$, find the maximum number of pairs that can be formed using objects of different types.
This is a well-known problem with the following solution. Let $$$tot$$$ be the total number of objects and $$$mx$$$ be the type that has the maximum number of objects (maximum value of $$$sz$$$). If the number of objects of type $$$mx$$$ is at most the number of all other objects (i. e. $$$sz_{mx} \le tot - sz_{mx}$$$), then we can pair all objects (except $$$1$$$ if the total number of objects is odd). Otherwise, we can create $$$tot - sz_{mx}$$$ pairs of the form $$$(mx, i)$$$ for all $$$i$$$ except $$$mx$$$.
Now we can return to the original problem. If the first aforementioned option is met for the root, then we know the answer to the problem is $$$\frac{tot}{2}$$$. Otherwise, we can create $$$tot - sz_{mx}$$$ pairs, but some nodes from the $$$mx$$$-th child's subtree are left unmatched (there are not enough vertices outside that subtree). So we can recursively look at the $$$mx$$$-th child subtree and solve the same problem. The only difference is that some number of vertices from that subtree are already matched. To solve this issue, we can add the parameter $$$k$$$ — how many vertices in the current subtree are already matched (we care only about the number of them). From the second paragraph, we know that the best situation (we can pair all objects) appears when the maximum value is at most the number of all other objects. Using this fact, we can say that $$$k$$$ matched vertices belong to the $$$mx$$$-th child's subtree. So we have to modify our check formula from $$$sz_{mx} \le tot - sz_{mx}$$$ to $$$sz_{mx} - k \le tot - sz_{mx}$$$. This process goes on until the current vertex (subtree) is a leaf or the condition is met.
This solution works in $$$O(n)$$$ if we precalculate the sizes for all the subtrees with a DFS before running it.