← 返回题目列表

Codeforces · 1665/C

C. 树感染

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

树是没有环的连通图。有根树有一个特殊的顶点,称为根。顶点 $$$v$$$ 的父顶点(与根不同)是从根到顶点 $$$v$$$ 的最短路径上 $$$v$$$ 顶点的前一个顶点。顶点 $$$v$$$ 的子节点都是以 $$$v$$$ 为父节点的顶点。

给你一棵有 $$$n$$$ 个顶点的有根树。顶点 $$$1$$$ 是根。最初,所有顶点都是健康的。

每秒执行两个操作,即扩散操作,然后是注入操作:

1. 传播:对于每个顶点 $$$v$$$,如果 $$$v$$$ 中至少有一个孩子被感染,则您最多可以通过感染您选择的 $$$v$$$ 中的其他一个孩子来传播疾病。
2.注射:可以选择任意健康的顶点进行感染。

这个过程每秒重复一次,直到整棵树被感染。您需要找到感染整棵树所需的最少秒数。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) - 给定树中的顶点数。

每个测试用例的第二行包含 $$$n - 1$$$ 整数 $$$p_2, p_3, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$),其中 $$$p_i$$$ 是树中第 $$$i$$$ 个顶点的祖先。

保证给定的图是一棵树。

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

输出

对于每个测试用例,您应该输出一个整数 - 感染整个树所需的最少秒数。

示例

输入 #1

5
7
1 1 1 2 2 4
5
5 5 1 4
2
1
3
3 1
6
1 1 1 1 1

输出 #1

4
4
2
3
4

注意

该图像描绘了每秒第一个测试用例中的树。

如果顶点未受感染,则其为黑色。如果顶点在前一秒内被注射感染,则该顶点呈蓝色。如果顶点在前一秒内因传播而受到感染,则该顶点呈绿色。如果顶点早于前一秒被感染,则该顶点呈红色。

请注意,您可以选择通过传播和注入感染哪些顶点。