まず、根である頂点 \(1\) は他のどの頂点から見ても祖先であるため、黒で塗ることはできません。

頂点 \(1\) を取り除いてできる森の各木の頂点数をそれぞれ \(C_1 \le C_2 \le \ldots \le C_K\) （ただし \(K\) は木の個数、つまり \(p_i=1\) となる \(i\) の個数）とします。答えの上界は \(\displaystyle 2\left\lfloor \frac12\sum_{i=1}^K C_i\right\rfloor=2\left\lfloor \frac{N-1}2\right\rfloor\) です。

もし \(\displaystyle C_K \le \sum_{i=1}^{K-1} C_i\) ならこの上界が達成可能です。具体的には、最も白が少ない（ただし頂点が全て黒の木は考えない）木と最も白が多い木の白を \(1\) つずつマッチングさせる操作を繰り返していけば良いです。

一方、\(\displaystyle C_K > \sum_{i=1}^{K-1} C_i\) なら大きさ \(C_K\) の部分木がネックとなります。したがって、大きさ \(C_K\) でない他 \(K-1\) 個の部分木は全て大きさ \(C_K\) の部分木とマッチングさせて良いです。

以上の一連の考察を最も大きい部分木に対して再帰的に行なっていけば良いです。具体的には、以下のアルゴリズムで答えを求めることができます。

1. \(\text{ans}=0,\text{z}=0,\text{now}=1\) とする。これらの変数はそれぞれ答え、マッチングできるが保留している頂点数、現在見ている部分木の根の頂点を表している。
2. 以下の 1. から 3. までを繰り返す。
   1. \(\text{z} > 0\) なら頂点 \(\text{now}\) を黒く塗ることができるので、 \(\text{z}\) を \(1\) 減らし \(\text{ans}\) を \(1\) 増やす。
   2. \(\text{now}\) のそれぞれの子を根とする部分木の頂点数を \(C_1 \le C_2\le \ldots \le C_K\) とする。
   3. \(\displaystyle C_K \le \sum_{i=1}^{K-1}C_i + z\) なら \(\text{ans}\) に \(\displaystyle \left\lfloor\frac12\left(\sum_{i=1}^{K}C_i+z \right) \right\rfloor\) を足してループを終了する。\(\displaystyle C_K >\sum_{i=1}^{K-1}C_i + z\) なら \(z\) に \(\displaystyle \sum_{i=1}^{K-1}C_i \) を足し \(\text{now}\) を部分木の大きさが最大である \(\text{now}\) の子に変更する。

以上を適切に実装することでこの問題に正答することができます。計算量は各テストケース毎に \(O(N)\) です。

実装例(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)