分数: 600 点
问题陈述
你得到了一棵有根的树 N 顶点编号自 1 to N。顶点 1 是根,也是顶点的父级 i (2 \le i \le N) 是顶点 p_i (1\le p_i < i)。最初,所有顶点都是白色的。
您可以执行以下操作序列零次或多次。
- 选择一对整数 (u,v) 满足以下所有条件。
- 1\le u < v \le N
- 两个顶点 u 和 v 为白色。
- u is 不 的祖先 v.
- 颜色顶点 u 和 v 黑色。
这里,“u 不是 v“意味着你无法到达顶点 u 从顶点 v 无论您执行多少次移动到当前顶点的父级的操作。
找出当您以适当的顺序执行操作时可以执行的最大操作数。
你被给予 T 测试用例,因此找到每个用例的答案。
约束
- 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.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
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
4 6 1 2 2 2 5 7 1 2 3 4 5 6 7 1 2 3 4 2 4 12 1 1 2 2 2 4 4 4 7 7 7
示例输出 1
2 0 2 5
考虑第一个测试用例。

您可以执行以下两个操作。
- 选择 (u,v)=(3,5)。颜色顶点 3 和 5 黑色。
- 选择 (u,v)=(4,6)。颜色顶点 4 和 6 黑色。
您不能执行两个以上的操作,因此输出 2 在第一行。