← 返回题目列表

Codeforces · 2031/E

E. 彭奇克和克洛伊的树

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

距离Penchick和Chloe出发前往新加坡只剩下几个小时了,他们迫不及待地想看看新加坡植物园的参天大树!为了抑制他们的兴​​奋,彭奇克制作了一棵有根的树,让克洛伊和他自己忙起来。

Penchick有一个有根树$$$^{\text{*}}$$$,由$$$n$$$个顶点组成,编号从$$$1$$$到$$$n$$$,以顶点$$$1$$$为根,Chloe可以选择一个非负整数$$$d$$$来创建完美的二元树$$$^{\text{†}}$$$,深度为$$$d$$$。

由于 Penchick 和 Chloe 是好朋友,Chloe 希望她的树与 Penchick 的树同构$$$^{\text{‡}}$$$。为了满足这个条件,Chloe 可以对她自己的树执行以下操作任意多次:

- 选择一条边 $$$(u,v)$$$,其中 $$$u$$$ 是 $$$v$$$ 的父级。
- 删除顶点 $$$v$$$ 以及连接到 $$$v$$$ 的所有边,然后将 $$$v$$$ 之前的所有子节点直接连接到 $$$u$$$。

特别是,在边 $$$(u, v)$$$ 上执行操作(其中 $$$v$$$ 是叶子)将删除顶点 $$$v$$$ 而不添加任何新边。

由于构建完美二叉树可能非常耗时,Chloe 希望选择最小值 $$$d$$$,以便使用上述操作可以使深度为 $$$d$$$ 的完美二叉树与 Penchick 树同构。请注意,她无法改变树的根。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^6$$$) — Penchick 树中的顶点数。

每个测试用例的第二行包含 $$$n-1$$$ 整数 $$$p_2, p_3, \ldots, p_n$$$ ($$$1 \leq p_i \leq i-1$$$) — 顶点 $$$i$$$ 的父节点。

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

输出

对于每个测试用例,在每一行输出一个整数:Chloe 完美二叉树的最小深度。

示例

输入 #1

5
6
1 2 2 1 1
15
1 1 2 2 3 3 4 4 5 5 6 6 7 7
5
1 2 2 2
7
1 1 2 1 1 2
10
1 1 1 2 2 2 4 3 3

输出 #1

2
3
3
3
3

注意

对于第一个测试用例,创建深度为 $$$2$$$ 的完美二叉树。

考虑在边 $$$AC$$$ 上执行操作。然后删除边 $$$AC$$$、$$$CF$$$ 和 $$$CG$$$,并添加边 $$$AF$$$ 和 $$$AG$$$。

生成的树与输入中给出的树同构。可以证明,对深度小于 $$$2$$$ 的二叉树执行的任何操作序列都不能产生与输入中给定的树同构的树。

在第二个测试用例中,树已经同构于深度 $$$3$$$ 的完美二叉树。