CF1827D.Two Centroids

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.

给你一棵树（一个无向、连通且无环的图），该树初始时仅包含顶点 $1$。接下来将对该树进行若干次查询。在第 $i$ 次查询中，顶点 $i + 1$ 将被加入，并与顶点 $p_i$ 相连（其中 $1 \le p_i \le i$）。

每次查询后，请计算使当前树恰好拥有两个重心所需的最少操作次数。每次操作允许你向树中添加一个顶点和一条边，且操作后图仍需保持为一棵树。

若删除某顶点后，所得各连通子树的大小均不超过 $\lfloor \frac{n}{2} \rfloor$（其中 $n$ 为树的顶点总数），则称该顶点为重心。例如，下图中顶点 $3$ 是重心，因为删去它后产生的最大子树含 $2$ 个顶点。

在下一棵树中，顶点 $1$ 和 $2$ 均为重心。

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

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 5 \cdot 10^{5}$）——表示最终树的节点数。

每个测试用例的第二行包含 $n - 1$ 个整数 $p_1, p_2, \ldots, p_{n - 1}$（$1 \le p_i \le i$）——表示与节点 $i + 1$ 相连的节点编号。

保证所有测试用例的 $n$ 之和不超过 $5 \cdot 10^{5}$。

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.

对于每个测试用例，输出 $n - 1$ 个整数。其中第 $i$ 个整数是第 $i$ 个查询的答案——即令当前树具有两个重心所需的最少操作次数。

可以证明答案一定存在。

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.

以下插图展示的是第四个示例测试用例。

第三次查询后：

此时树中顶点 $2$ 和 $3$ 已是重心，因此无需执行任何操作。

第四次查询后：

向树中添加顶点 $x$ 后，顶点 $2$ 和 $3$ 成为重心。仅需执行一次操作。

第五次查询后：

向树中添加顶点 $x$ 和 $y$ 后，顶点 $5$ 和 $2$ 成为重心。需要执行两次操作。

第六次查询后：

向树中添加顶点 $x$、$y$ 和 $z$ 后，顶点 $5$ 和 $2$ 成为重心。需要执行三次操作。