A10565 | 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.

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$ .