First, vertex \(1\), which is the root, is an ancestor of any other vertex, so it cannot be colored black.

Let \(C_1 \le C_2 \le \ldots \le C_K\) be the number of vertices in each tree of the forest created by removing vertex \(1\) (where \(K\) is the number of trees, i.e., the number of \(i\) such that \(p_i=1\)). An upper bound of the answer is \(\displaystyle 2\left\lfloor \frac12\sum_{i=1}^K C_i\right\rfloor=2\left\lfloor \frac{N-1}2\right\rfloor\).

If \(\displaystyle C_K \le \sum_{i=1}^{K-1} C_i\), then this upper bound is achievable. Specifically, we can repeatedly perform the operation of matching one white vertex each from the tree with the fewest white vertices (excluding trees where all vertices are black) and the tree with the most white vertices.

On the other hand, if \(\displaystyle C_K > \sum_{i=1}^{K-1} C_i\), then the subtree of size \(C_K\) becomes a bottleneck. Therefore, all other \(K-1\) subtrees not of size \(C_K\) can be matched with the subtree of size \(C_K\).

We can recursively apply the above series of considerations to the largest subtree. Specifically, the answer can be found using the following algorithm:

1. Set \(\text{ans}=0,\text{z}=0,\text{now}=1\). These variables represent the answer, the number of vertices that can be matched but are on hold, and the root vertex of the current subtree, respectively.
2. Repeat the following steps 1 to 3:
   1. If \(\text{z} > 0\), vertex \(\text{now}\) can be colored black, so decrease \(\text{z}\) by \(1\) and increase \(\text{ans}\) by \(1\).
   2. Let \(C_1 \le C_2\le \ldots \le C_K\) be the number of vertices in the subtrees rooted at each child of \(\text{now}\).
   3. If \(\displaystyle C_K \le \sum_{i=1}^{K-1}C_i + z\), add \(\displaystyle \left\lfloor\frac12\left(\sum_{i=1}^{K}C_i+z \right) \right\rfloor\) to \(\text{ans}\) and end the loop. If \(\displaystyle C_K >\sum_{i=1}^{K-1}C_i + z\), add \(\displaystyle \sum_{i=1}^{K-1}C_i\) to \(z\) and change \(\text{now}\) to the child of \(\text{now}\) with the largest subtree size.

By implementing this appropriately, we can solve this problem. The time complexity is \(O(N)\) per test case.

Implementation Example (Python3)

import sys

input = sys.stdin.readline
for _ in range(int(input())):
    n = int(input())
    p = list(map(int, input().split()))
    g = [[] for _ in range(n)]
    for i in range(1, n):
        g[p[i - 1] - 1].append(i)
    sz = [1] * n
    for i in reversed(range(n)):
        for x in g[i]:
            sz[i] += sz[x]
    ans, z, now = 0, 0, 0
    while True:
        if z > 0:
            ans += 1
            z -= 1
        c = []
        for i in g[now]:
            c.append(sz[i])
        max_c, sum_c, max_idx = 0, 0, -1
        for i in range(len(c)):
            if max_c < c[i]:
                max_c = c[i]
                max_idx = g[now][i]
            sum_c += c[i]
        if sum_c - max_c + z >= max_c:
            ans += (sum_c + z) // 2
            break
        z += sum_c - max_c
        now = max_idx
    print(ans)