← 返回题目列表

Codeforces · 1827/D

D. 两个质心

中文机器翻译题面 查看原题

给你一棵树(无向连通无环图),它最初只包含顶点 $$$1$$$。对给定的树将会有多个查询。在第 $$$i$$$ 查询中,顶点 $$$i + 1$$$ 将出现并连接到顶点 $$$p_i$$$ ($$$1 \le p_i \le i$$$)。

每次查询后,请找出使当前树有两个质心所需的最少操作次数。在一次操作中,您可以向树添加一个顶点和一条边,使其保持为一棵树。

一个顶点被称为质心,如果它的移除将树分割成子树,每个子树最多具有 $$$\lfloor \frac{n}{2} \rfloor$$$ 个顶点,其中 $$$n$$$ 作为树的顶点数。例如,下面的树的质心是$$$3$$$,因为删除质心后最大的子树有$$$2$$$个顶点。

在下一棵树中,顶点 $$$1$$$ 和 $$$2$$$ 都是质心。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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}$$$。

输出

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

我们可以证明答案总是存在的。

示例

输入 #1

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

输出 #1

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

注意

下图是第四个示例测试用例。

第三次查询后:

第四次查询后:

第五次查询后:

第六次查询后: