← 返回题目列表

Codeforces · 842/E

E. 尼基塔和游戏

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

Nikita 玩一个新的电脑游戏。这个游戏有m个关卡。在每个关卡开始时,游戏中都会出现一个新职业;这个类是 yi 类的子类(并且 yi 被称为这个新类的父类)。因此,类形成一棵树。最初只有一个索引为 1 的类。

将类更改为树中的邻居(子类或父类)需要 1 个硬币。您无法将班级更改回来。将类a更改为类b的成本等于类树中从a到b的路径上类更改的总成本。

假设在第 i 级,将一个类别更改为另一个类别的最大成本为 x。对于每个级别输出类的数量,使得对于每个类都存在一些其他类 y,并且从该类到 y 的距离恰好为 x。

输入

第一行包含一个整数 m — 查询数 (1 ≤ m ≤ 3·105)。

接下来的 m 行包含查询的描述。第 i 行 (1 ≤ i ≤ m) 描述第 i 个级别并包含一个整数 yi - 索引为 i + 1 (1 ≤ yi ≤ i) 的类的父类的索引。

输出

假设在第 i 级,将一个类别更改为另一个类别的最大成本为 x。对于每个级别输出类的数量,使得对于每个类都存在一些其他类 y,并且从该类到 y 的距离恰好为 x。

示例

输入 #1

4
1
1
2
1

输出 #1

2
2
2
3

输入 #2

4
1
1
2
3

输出 #2

2
2
2
2