← 返回题目列表

Codeforces · 2006/E

E. Iris 的完整二叉树

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

Iris 喜欢完整二叉树。

让我们将有根树的深度定义为从某个顶点到根的简单路径上的最大顶点数。深度为 $$$d$$$ 的满二叉树是深度为 $$$d$$$ 且恰好有 $$$2^d - 1$$$ 个顶点的二叉树。

如果可以向树添加一些顶点和边以使其成为深度为 $$$d$$$ 的完整二叉树,则 Iris 将树称为 $$$d$$$ 二叉树。请注意,可以选择任何顶点作为满二叉树的根。

由于对大树执行操作很困难,她将树的二元深度定义为满足树是二元的 $$$d$$$ 的最小值。具体来说,如果不存在整数 $$$d \ge 1$$$ 使得树是 $$$d$$$-二叉树,则树的二叉树深度为 $$$-1$$$。

Iris 现在有一棵仅由顶点 $$$1$$$ 组成的树。她想添加 $$$n - 1$$$ 个顶点以形成一棵更大的树。她将一一添加顶点。当她添加顶点 $$$i$$$ ($$$2 \leq i \leq n$$$) 时,她会给你一个整数 $$$p_i$$$ ($$$1 \leq p_i < i$$$),并添加一条连接顶点 $$$i$$$ 和 $$$p_i$$$ 的新边。

Iris 想询问您每个 $$$1 \le i \le n$$$ 的第一个 $$$i$$$ 顶点形成的树的二元深度。你能告诉她答案吗?

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 5 \cdot 10^5$$$) — 树的最终大小。

每个测试用例的第二行包含 $$$n - 1$$$ 整数 $$$p_2, p_3, \ldots, p_n$$$ ($$$1 \leq p_i < i$$$) - 树所有边的描述。

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

输出

对于每个测试用例输出 $$$n$$$ 个整数,其中 $$$i$$$ 表示由第一个 $$$i$$$ 顶点形成的树的二进制深度。

示例

输入 #1

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

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

注意

在第一个测试用例中,最终的树如下所示:

- 由顶点 $$$1$$$ 组成的树具有二元深度 $$$1$$$ (树本身是深度为 $$$1$$$ 的完整二叉树)。
- 由顶点 $$$1$$$ 和 $$$2$$$ 组成的树具有二元深度 $$$2$$$ (我们可以添加顶点 $$$3$$$ 使其成为深度为 $$$2$$$ 的完整二叉树)。
- 由顶点 $$$1$$$、$$$2$$$ 和 $$$3$$$ 组成的树具有二元深度 $$$2$$$ (树本身是深度为 $$$2$$$ 的完整二叉树)。

在第二个测试用例中,向由$$$n$$$个顶点组成的树添加一些顶点后形成的满二叉树如下所示(添加了粗体顶点):

形成的满二叉树的深度为$$$4$$$。

在第五个测试用例中,最终的树如下所示:

可以证明,Iris 不能通过添加顶点和边来形成任意满二叉树,因此二叉深度为$$$-1$$$。