CF1914F Programming Competition

BerSoft 是 Berland 最大的 IT 公司。公司共有 $n$ 名员工，编号从 $1$ 到 $n$。 第 $1$ 号员工是公司的负责人，他没有上级。每个其他员工 $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$。

对于每个测试用例，输出一个整数，表示在上述规则下最多可以组建的队伍数。

在第一个测试用例中，可以组建队伍 $(3, 4)$。 在第二个测试用例中，无法组队，因为只有两名员工且一人为另一人的上级。 在第三个测试用例中，可以组建队伍 $(2, 3)$。 在第四个测试用例中，可以组建队伍 $(2, 4)$、$(3, 5)$ 和 $(6, 7)$。 在第五个测试用例中，可以组建队伍 $(2, 3)$、$(6, 4)$ 和 $(5, 7)$。 由 ChatGPT 4.1 翻译