← 返回题目列表

Codeforces · 690/C3

C3. 大脑网络(硬)

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

僵尸神经病学的重大新闻!事实证明,与之前的看法相反,每个僵尸生来都有一个大脑,只是后来才进化成一个复杂的大脑结构。事实上,每当僵尸消耗一个大脑时,它的神经系统中就会出现一个新的大脑,并立即使用单个大脑连接器连接到现有的大脑之一。研究人员现在对监测僵尸的大脑潜伏期感兴趣。你的任务是编写一个程序,根据僵尸神经系统的进化历史,计算其每个阶段的大脑潜伏期。

输入

输入的第一行包含一个数字 n – 最终神经系统中的大脑数量 (2 ≤ n ≤ 200000)。第二行给出了僵尸神经系统进化的历史。为了方便起见,我们按照神经系统中出现的顺序将所有大脑编号为 1, 2, ..., n(僵尸出生时只有一个大脑,编号为 1,随后添加大脑 2, 3, ..., n)。第二行包含 n - 1 个空格分隔的数字 p2, p3, ..., pn,这意味着在将新大脑 k 添加到系统后,它会连接到父大脑 $$p_k \in \{1, 2, \ldots, k-1\}$$。

输出

输出 n - 1 个空格分隔的数字 – 添加大脑数字 k 后的大脑延迟,其中 k = 2, 3, ..., n。

示例

输入 #1

6
1
2
2
1
5

输出 #1

1 2 2 3 4