Brain Network (hard)

题意翻译

给你一个 $1$ 个节点的树，有 $n-1$ 次操作。对于第 $i$ 次操作，新增一个节点 $i+1$ 并把它连向 $p_i$ （ $p_i<i+1$ ）。请在每次操作之后，求出树的直径。 $2\le n\le 2\times 10^5$

题目描述

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.

输入输出格式

输入格式

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 .

输出格式

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

输入输出样例

输入样例 #1

6
1
2
2
1
5

输出样例 #1

1 2 2 3 4