310406: CF1828F. Two Centroids

F. Two Centroidstime limit per test1.5 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

You are given a tree (an undirected connected acyclic graph) which initially only contains vertex $1$. There will be several queries to the given tree. In the $i$-th query, vertex $i + 1$ will appear and be connected to vertex $p_i$ ($1 \le p_i \le i$).

After each query, please find out the least number of operations required to make the current tree has two centroids. In one operation, you can add one vertex and one edge to the tree such that it remains a tree.

A vertex is called a centroid if its removal splits the tree into subtrees with at most $\lfloor \frac{n}{2} \rfloor$ vertices each, with $n$ as the number of vertices of the tree. For example, the centroid of the following tree is $3$ because the biggest subtree after removing the centroid has $2$ vertices.

In the next tree, vertex $1$ and $2$ are both centroids.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \le n \le 5 \cdot 10^{5}$) — the number of nodes of the final tree.

The second line of each test case contains $n - 1$ integers $p_1, p_2, \ldots, p_{n - 1}$ ($1 \le p_i \le i$) — the index of the vertex that is connected to vertex $i + 1$.

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 - 1$ integers. The $i$-th integer is the answer to the $i$-th query — the least number of operations required to make the current tree have two centroids.

We can show that an answer always exists.

ExampleInput

5
2
1
3
1 1
4
1 2 3
7
1 2 3 2 5 2
10
1 2 2 4 5 5 7 8 9

Output

0
0 1
0 1 0
0 1 0 1 2 3
0 1 2 1 0 1 0 1 2

Note

The illustrations below are of the fourth example test case.

After the third query:

The tree already has vertices $2$ and $3$ as centroids, so no operations are needed.

After the fourth query:

Adding vertex $x$ to the tree makes vertices $2$ and $3$ centroids. Only one operation is needed.

After the fifth query:

Adding vertex $x$ and $y$ to the tree makes vertices $5$ and $2$ centroids. Two operations are needed.

After the sixth query:

Adding vertex $x$, $y$, and $z$ to the tree makes vertices $5$ and $2$ centroids. Three operations are needed.

题目大意：给定一棵初始仅包含顶点1的树（无向连通无环图），会有多次查询操作。在第i次查询时，顶点i+1会出现并连接到顶点p_i（1≤p_i≤i）。每次查询后，请找出使当前树具有两个质心所需的最少操作数。在一次操作中，你可以向树中添加一个顶点和一条边，使得它仍然是一棵树。

质心定义：如果删除一个顶点后，树被分割成每个子树最多有⌊n/2⌋个顶点的子树，那么这个顶点称为质心，其中n是树中顶点的数量。

输入数据格式：每个测试用例包含多个测试案例。第一行包含测试案例的数量t（1≤t≤10^4）。接下来是每个测试案例的描述。
每个测试案例的第一行包含一个整数n（2≤n≤5×10^5）——最终树的节点数。
每个测试案例的第二行包含n-1个整数p_1, p_2, ..., p_{n-1}（1≤p_i≤i）——连接到顶点i+1的顶点的索引。

输出数据格式：对于每个测试案例，输出n-1个整数。第i个整数是第i个查询的答案——使当前树具有两个质心所需的最少操作数。

示例输入输出已给出，具体可参考原文中的Example部分。题目大意：给定一棵初始仅包含顶点1的树（无向连通无环图），会有多次查询操作。在第i次查询时，顶点i+1会出现并连接到顶点p_i（1≤p_i≤i）。每次查询后，请找出使当前树具有两个质心所需的最少操作数。在一次操作中，你可以向树中添加一个顶点和一条边，使得它仍然是一棵树。 质心定义：如果删除一个顶点后，树被分割成每个子树最多有⌊n/2⌋个顶点的子树，那么这个顶点称为质心，其中n是树中顶点的数量。 输入数据格式：每个测试用例包含多个测试案例。第一行包含测试案例的数量t（1≤t≤10^4）。接下来是每个测试案例的描述。 每个测试案例的第一行包含一个整数n（2≤n≤5×10^5）——最终树的节点数。 每个测试案例的第二行包含n-1个整数p_1, p_2, ..., p_{n-1}（1≤p_i≤i）——连接到顶点i+1的顶点的索引。 输出数据格式：对于每个测试案例，输出n-1个整数。第i个整数是第i个查询的答案——使当前树具有两个质心所需的最少操作数。 示例输入输出已给出，具体可参考原文中的Example部分。