CF690C3 Brain Network (hard)

来自僵尸神经学的爆炸性新闻！事实证明——与先前的看法相反——每只僵尸出生时只有一个大脑，之后才会进化出复杂的大脑结构。实际上，每当一只僵尸吞食一个大脑时，它的神经系统中就会出现一个新大脑，并立即通过一根大脑连接器与已存在的大脑之一相连。研究人员现在对监测僵尸的大脑延迟很感兴趣。你的任务是，给定僵尸神经系统进化的历史，编写程序计算每个阶段的大脑延迟。

输入的第一行包含一个数字 $n$——最终神经系统中的大脑数量（$2 \leq n \leq 200000$）。第二行给出了僵尸神经系统进化的历史。为方便起见，我们将所有大脑按它们在神经系统中出现的顺序编号为 $1,2,\ldots,n$（僵尸出生时拥有编号为 $1$ 的大脑，随后依次添加编号为 $2,3,\ldots,n$ 的大脑）。第二行包含 $n-1$ 个用空格分隔的数字 $p_2, p_3, \ldots, p_n$，表示每当新大脑 $k$ 被添加到系统中时，它会通过一根连接器与编号为 $p_k$ 的父大脑相连。

输出 $n-1$ 个用空格分隔的数字——分别表示每次添加编号为 $k$ 的大脑后（$k=2,3,\ldots,n$）的僵尸大脑延迟。

由 ChatGPT 4.1 翻译