303574: CF690C3. Brain Network (hard)

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF690C3/b7b76d65e68a74cf783f112f6bfb091b261aef80.png).

输出格式


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 

Input

题意翻译

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

加入题单

上一题 下一题 算法标签: