← 返回题目列表

Codeforces · 1739/D

D. 复位 K 边沿

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

给你一棵有根树,由 $$$n$$$ 个顶点组成。顶点编号从$$$1$$$到$$$n$$$,根是顶点$$$1$$$。

您最多可以执行以下操作 $$$k$$$ 次:

- 选择树的边 $$$(v, u)$$$,使得 $$$v$$$ 是 $$$u$$$ 的父级;
- 删除边 $$$(v, u)$$$;
- 添加一条边 $$$(1, u)$$$ (即,使 $$$u$$$ 及其子树成为根的子树)。

树的高度是其顶点的最大深度,顶点的深度是从根到它的路径上的边数。例如,顶点 $$$1$$$ 的深度为 $$$0$$$,因为它是根,并且其所有子节点的深度为 $$$1$$$。

树的最小高度是多少?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$0 \le k \le n - 1$$$) - 树中的顶点数和可以执行的最大操作数。

第二行包含 $$$n-1$$$ 整数 $$$p_2, p_3, \dots, p_n$$$ ($$$1 \le p_i < i$$$) — 第 $$$i$$$ 个顶点的父顶点。顶点 $$$1$$$ 是根。

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

输出

对于每个测试用例,打印一个整数 - 通过执行最多 $$$k$$$ 操作可以获得的树的最小高度。

示例

输入 #1

5
5 1
1 1 2 2
5 2
1 1 2 2
6 0
1 2 3 4 5
6 1
1 2 3 4 5
4 3
1 1 1

输出 #1

2
1
5
3
1