Iris's Full Binary Tree
Contest: Codeforces Round 969 (Div. 1)
Difficulty rating: 3100
Tags: brute force, data structures, dfs and similar, trees

Iris likes full binary trees.

Let's define the depth of a rooted tree as the maximum number of vertices on the simple paths from some vertex to the root. A full binary tree of depth $$$d$$$ is a binary tree of depth $$$d$$$ with exactly $$$2^d - 1$$$ vertices.

Iris calls a tree a $$$d$$$-binary tree if some vertices and edges can be added to it to make it a full binary tree of depth $$$d$$$. Note that any vertex can be chosen as the root of a full binary tree.

Since performing operations on large trees is difficult, she defines the binary depth of a tree as the minimum $$$d$$$ satisfying that the tree is $$$d$$$-binary. Specifically, if there is no integer $$$d \ge 1$$$ such that the tree is $$$d$$$-binary, the binary depth of the tree is $$$-1$$$.

Iris now has a tree consisting of only vertex $$$1$$$. She wants to add $$$n - 1$$$ more vertices to form a larger tree. She will add the vertices one by one. When she adds vertex $$$i$$$ ($$$2 \leq i \leq n$$$), she'll give you an integer $$$p_i$$$ ($$$1 \leq p_i < i$$$), and add a new edge connecting vertices $$$i$$$ and $$$p_i$$$.

Iris wants to ask you the binary depth of the tree formed by the first $$$i$$$ vertices for each $$$1 \le i \le n$$$. Can you tell her the answer?

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 5 \cdot 10^5$$$) — the final size of the tree.

The second line of each test case contains $$$n - 1$$$ integers $$$p_2, p_3, \ldots, p_n$$$ ($$$1 \leq p_i < i$$$) — descriptions of all edges of the tree.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.

Output format:
For each test case output $$$n$$$ integers, $$$i$$$-th of them representing the binary depth of the tree formed by the first $$$i$$$ vertices.

Constraints:
Time limit: 4.0 s
Memory limit: 1024.0 MB

Note:
In the first test case, the final tree is shown below:

- The tree consisting of the vertex $$$1$$$ has the binary depth $$$1$$$ (the tree itself is a full binary tree of depth $$$1$$$).
- The tree consisting of the vertices $$$1$$$ and $$$2$$$ has the binary depth $$$2$$$ (we can add the vertex $$$3$$$ to make it a full binary tree of depth $$$2$$$).
- The tree consisting of the vertices $$$1$$$, $$$2$$$ and $$$3$$$ has the binary depth $$$2$$$ (the tree itself is a full binary tree of depth $$$2$$$).

In the second test case, the formed full binary tree after adding some vertices to the tree consisting of $$$n$$$ vertices is shown below (bolded vertices are added):

The depth of the formed full binary tree is $$$4$$$.

In the fifth test case, the final tree is shown below:

It can be proved that Iris can't form any full binary tree by adding vertices and edges, so the binary depth is $$$-1$$$.

Example input:
7
3
1 1
6
1 2 3 4 5
7
1 1 3 2 5 1
10
1 1 2 1 4 2 4 5 8
10
1 1 3 1 3 2 2 2 6
20
1 1 2 2 4 4 5 5 7 6 8 6 11 14 11 8 13 13 12
25
1 1 3 3 1 5 4 4 6 8 11 12 8 7 11 13 7 13 15 6 19 14 10 23

Example output:
1 2 2 
1 2 2 3 3 4 
1 2 2 3 3 4 4 
1 2 2 3 3 3 4 4 5 5 
1 2 2 3 3 4 4 4 -1 -1 
1 2 2 3 3 4 4 4 4 5 5 5 5 6 6 6 6 6 6 7 
1 2 2 3 3 4 4 4 4 5 5 6 6 6 6 6 7 7 7 7 7 8 8 8 8

Editorial:
Here're two lemmas that will be used in the solution.
Lemma 1: Among all the points on a tree with the greatest distance from a certain point, one of which must be one of the two endpoints of a certain diameter.
Lemma 2: After merging two trees, at least one new diameter is generated at the four endpoints of two certain diameters.
Obviously, we consider a subtree composed of the first $$$k$$$ points, which corresponds to a fully binary tree with a depth of $$$d$$$, and must have only one node with the smallest depth (otherwise it would not be connected). If the depth of the node with the smallest depth is greater than $$$1$$$, then we can reduce the depth of all nodes by $$$1$$$. It is easy to see that this will not cause conflicts, and $$$d$$$ should be reduced by $$$1$$$.
In this case, we obtain:
Conclusion 1: There must be a node corresponding to the root of a fully binary tree.
Meanwhile, due to the degrees of the nodes of a full binary tree, it is obtained that:
Conclusion 2: The node corresponding to the root should have a degree $$$\leq 2$$$; if there is a node with a degree $$$\gt 3$$$, then all subsequent queries should be $$$d = -1$$$.
We can consider the case where each point is the root, and due to the Lemma, we can obtain $$$d$$$ as the maximum distance from that point to the endpoints of two diameters, then plus $$$1$$$. Finally, select the point with degree $$$\leq 2$$$ that minimizes this maximum value as the root.
Brute practices can achieve $$$\mathcal O(n^2\log n)$$$ time. Consider optimization.
According to Lemma 2, each time a point is added, the diameter length either remains unchanged or increases by $$$1$$$. In the case of adding $$$1$$$, as mentioned earlier, we investigate the maximum distance of all points (temporarily ignoring their degrees).
If we consider real-time maintenance of its changes, it is obvious that if the new diameter distance is even, it is equivalent to a maximum distance of $$$+1$$$ for all points except for a subtree at the midpoint of the new diameter; otherwise, it is equivalent to a maximum distance of $$$+1$$$ for all points of the subtree at the midpoint of the original diameter. Pay attention to the subtrees mentioned, where the roots of the entire tree are variable, but this is not very important.
We can traverse and number all nodes in the DFS order, so that the subtree of each node is within an interval in such order. Therefore, an indefinite rooted subtree can also be represented by $$$\mathcal O(1)$$$ intervals. You can use a segment tree to facilitate the maintenance of the $$$+1$$$ operations.
In addition, considering the impact of degrees, we just need to increase the maximum distance of a $$$3$$$-degreed node by $$$+\inf$$$. Ultimately, at the end of each operation, we need only the global minimum value.
The time complexity is $$$O (n\log n)$$$.