CF842E Nikita and game

Nikita 玩一个新的电脑游戏。在这个游戏中有 $m$ 个关卡。每过一关，游戏中就会出现一个新类，这个新类是类 $y_i$ 的子类（并且 $y_i$ 被称作这个新类的父类）。因此，这些类会形成一棵树。初始时，只有编号为 $1$ 的一个类。 在这棵树中，从一个类切换到其相邻类（子类或父类）需要花费 $1$ 个金币。你不能回到上一个类。从类 $a$ 切换到类 $b$ 的花费等于在类树中从 $a$ 到 $b$ 路径上所有切换的总花费。 假设在第 $i$ 个关卡时，切换类所需要的最大花费为 $x$。对于每个关卡，输出满足如下条件的类的个数：对于每一个这样的类，都存在某些其他类 $y$，并且从该类到 $y$ 的距离恰好为 $x$。

第一行包含一个整数 $m$，表示查询个数（$1\leq m\leq 3\cdot10^{5}$）。 接下来的 $m$ 行，每行包含一个整数 $y_i$，表示编号为 $i+1$ 的类的父类索引（$1\leq y_i\leq i$）。

假设在第 $i$ 关时，切换一个类到另一个类所需的最大花费为 $x$。对于每个关卡，输出满足对于每个这样的类，都存在某个其它类 $y$，且从该类到 $y$ 的距离正好为 $x$ 的类的数量。

由 ChatGPT 5 翻译