CF690C3.Brain Network (hard)

Breaking news from zombie neurology! It turns out that – contrary to previous beliefs – every zombie is born with a single brain, and only later it evolves into a complicated brain structure. In fact, whenever a zombie consumes a brain, a new brain appears in its nervous system and gets immediately connected to one of the already existing brains using a single brain connector. Researchers are now interested in monitoring the brain latency of a zombie. Your task is to write a program which, given a history of evolution of a zombie's nervous system, computes its brain latency at every stage.

僵尸神经学最新消息！事实证明，与先前的认知相反——每个僵尸出生时都仅拥有一个大脑，之后才逐渐演化为复杂的大脑结构。实际上，每当僵尸摄取一个大脑时，其神经系统中便会立即生成一个新的大脑，并通过一条脑连接器（brain connector） 与已存在的某个大脑直接相连。目前，研究人员希望监测僵尸的脑延迟（brain latency）。你的任务是编写一个程序，根据僵尸神经系统演化的历史记录，计算其在每一阶段的脑延迟。

The first line of the input contains one number n – the number of brains in the final nervous system (2 ≤ n ≤ 200000). In the second line a history of zombie's nervous system evolution is given. For convenience, we number all the brains by 1, 2, ..., n in the same order as they appear in the nervous system (the zombie is born with a single brain, number 1, and subsequently brains 2, 3, ..., n are added). The second line contains n - 1 space-separated numbers _p_2, _p_3, ..., p__n, meaning that after a new brain k is added to the system, it gets connected to a parent-brain .

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

Output n - 1 space-separated numbers – the brain latencies after the brain number k is added, for k = 2, 3, ..., n.

输出 $n-1$ 个空格分隔的数字——即依次添加脑编号 $k$ 后的脑延迟值，其中 $k = 2, 3, \dots, n$。