← 返回题目列表

AtCoder · arc205_d

D. 非祖先匹配

中文机器翻译题面 查看原题

分数: 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 在第一行。