AT_arc205_d [ARC205D] Non-Ancestor Matching

给定一棵有 $N$ 个顶点的有根树，顶点编号为 $1$ 到 $N$。顶点 $1$ 是根节点，顶点 $i$ 的父节点为 $p_i$（$2 \le i \le N$，$1\le p_i < i$）。最初，所有顶点均被染为白色。 你可以执行如下操作任意多次（包括零次）： - 选择一对整数 $(u,v)$，满足以下所有条件： - $1\le u < v \le N$ - 顶点 $u$ 和 $v$ 都是白色。 - $u$ 不是 $v$ 的祖先。 - 将顶点 $u$ 和 $v$ 染为黑色。 这里，$u$ 不是 $v$ 的祖先，表示无论你对 $v$ 向上传递到父节点多少次，都无法到达 $u$。 请你在合适的操作顺序下，计算你最多可以执行多少次操作。 有 $T$ 组测试数据，请你求出每组的答案。

输入按如下格式给出： > $T$ > > $\text{case}_1$ > > $\text{case}_2$ > > $\vdots$ > > $\text{case}_T$ 每组测试数据 $\text{case}_i$ 格式如下： > $N$ > > $p_2$ $p_3$ $\ldots$ $p_N$

输出 $T$ 行。 第 $i$ 行（$1\le i\le T$）输出第 $i$ 个测试用例的答案。

### 示例解释 1 考虑第一个测试用例。  你可以如下进行两次操作： - 选择 $(u,v)=(3,5)$，将顶点 $3$ 和 $5$ 染成黑色。 - 选择 $(u,v)=(4,6)$，将顶点 $4$ 和 $6$ 染成黑色。 无法进行超过两次的操作，因此第一行输出 $2$。 ### 数据范围 - $1\le T\le 5\times 10^4$ - $2\le N\le 5\times 10^5$ - $1\le p_i < i$ - 所有测试用例的 $N$ 之和不超过 $5\times 10^5$。 - 所有输入值均为整数。 由 ChatGPT 5 翻译