Dynamic Centroid

Time limit1.5sMemory limit512 MB

Summary

For each prefix tree formed by vertices 1..k, output the smallest centroid (the vertex whose removal leaves components of size at most k/2).

Level: Hard8 of 10
Topics: Tree, DFS, Greedy, Dynamic programming
Solved: No attempts yet

Problem

In a tree with $N$ vertices, a centroid is a vertex such that every subtree obtained by splitting the tree at that vertex has size at most $N/2$ . Every tree is known to have a centroid.

Vertex 1 is the root of the tree, the parent of vertex $i$ is $p_i$ , and $p_i < i$ .

For each $k$ from $1$ to $N$ , find the centroid of the tree that uses only vertices 1 through $k$ .

Input

The first line gives $N$ . ( $2 \le N \le 5 \times 10^5$ )

The second line gives $p_i$ for $i = 2$ through $i = N$ , separated by spaces. ( $1 \le p_i < i$ )

Output

For each $k$ from $1$ to $N$ , print the number of the centroid of the tree that uses only vertices 1 through $k$ , separated by spaces, in order. If several answers exist, print the smallest one.

Examples2

Example 1
Input
```
5
1 2 3 4
```
Expected output
```
1 1 2 2 3 
```
Example 2
Input
```
5
1 2 1 4
```
Expected output
```
1 1 2 1 1 
```