← 返回题目列表

Codeforces · 1914/F

F. 编程竞赛

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

BerSoft 是 Berland 最大的 IT 公司。 BerSoft 公司共有 $$$n$$$ 名员工,编号从 $$$1$$$ 到 $$$n$$$。

第一位员工是公司的负责人,他没有任何上级。每一位其他员工 $$$i$$$ 都有一位直接上级 $$$p_i$$$。

如果满足以下条件之一,员工 $$$x$$$ 被视为员工 $$$y$$$ 的上级(直接或间接):

- 员工$$$x$$$是员工$$$y$$$的直接上级;
- 员工$$$x$$$ 是员工$$$y$$$ 的直接上级的上级。

BerSoft 的组织结构是公司负责人高于每位员工。

编程比赛即将举行。为此目的应创建两人团队。然而,如果团队中的一名员工是另一名员工的上级,他们在一起就会感到不舒服。因此,应该创建两个人的团队,这样就没有一个人比另一个人更优越。请注意,任何员工都不能参与多个团队。

你的任务是根据上述规则计算最大可能的团队数量。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 员工数量。

第二行包含 $$$n-1$$$ 整数 $$$p_2, p_3, \dots, p_n$$$ ($$$1 \le p_i \le n$$$),其中 $$$p_i$$$ 是第 $$$i$$$ 员工的直接上级的索引。

所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - 根据上述规则的最大可能团队数量。

示例

输入 #1

6
4
1 2 1
2
1
5
5 5 5 1
7
1 2 1 1 3 3
7
1 1 3 2 2 4
7
1 2 1 1 1 3

输出 #1

1
0
1
3
3
3

注意

在第一个测试用例中,可以创建团队$$$(3, 4)$$$。

在第二个测试用例中,无法创建任何团队,因为只有 $$$2$$$ 员工,并且其中一个是另一个的上级。

在第三个测试用例中,可以创建团队$$$(2, 3)$$$。

在第四个测试用例中,可以创建团队 $$$(2, 4)$$$、$$$(3, 5)$$$ 和 $$$(6, 7)$$$。

在第五个测试用例中,可以创建团队 $$$(2, 3)$$$、$$$(6, 4)$$$ 和 $$$(5, 7)$$$。