codeforces#P2006E. Iris's Full Binary Tree

    ID: 34897 远端评测题 4000ms 1024MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>brute forcedata structuresdfs and similartrees

Iris's Full Binary Tree

Description

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?

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

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

Input

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

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

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

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