解题思路

题目要求在一棵以 $1$ 为根的树上选择最多 $k$ 个关键审批节点，使得每个节点都能在向祖先方向走不超过 $D$ 条边后到达某个关键节点，求最小的 $D$。

可以对答案 $D$ 进行二分，然后判断当前 $D$ 是否可行。

判断可行性时使用贪心算法：

从深度最大的节点开始处理。

题目内容

多多的部门中发起审批单有一套审批流程，审批关系可以抽象为一棵以 $1$ 号节点为根的树，共有 $n$ 个节点。对于每个 $i(2 \le i \le n)$，给定它的直属上级 $p_i$，即审批树中存在一条从 $p_i$ 到 $i$ 的边。

对于任意节点 $u$，如果它发起一张审批单，那么审批单只能先提交给它的直属上级，再继续逐级上报到更高层。

现在多多最多可以选择 $k$ 个节点作为“关键审批节点”。如果审批单从 $u$ 出发，向上经过不超过 $D$ 条边，就能够到达某个关键审批节点，则称节点 $u$ 被覆盖。

请帮多多找到，在最多选择 $k$ 个关键审批节点的前提下，求出满足条件的最小 $D$，使得整棵审批树上的所有节点都被覆盖。

输入描述

第一行输入一个整数 $T(1 \le T \le 3)$，表示数据组数。 接下来对于每组数据：

• 第一行包含两个整数 $n(1 \le n \le 2 \times 10^5)$ 和 $k(1 \le k \le n)$。
• 第二行包含 $n-1$ 个整数 $p_2, p_3, \dots, p_n$，其中 $p_i$ 表示节点 $i$ 的父节点。

输出描述

对于每组数据，仅输出一行整数，表示满足条件的最小 $D$。

样例1

输入

1
7 2
1 1 2 2 3 3

输出

2

说明

可以把节点 $1$ 和 $2$ 设置为关键审批节点。

• 节点 $1、2$ 自身被覆盖；
• 节点 $3$ 向上走 $1$ 条边可以到达节点 $1$；
• 节点 $4、5$ 向上走 $1$ 条边可以到达节点 $2$；
• 节点 $6、7$ 向上走 $2$ 条边可以到达节点 $1$。

样例2

输入

1
5 1
1 2 3 4

输出

4

说明

这是一条长度为 $4$ 的链。

如果只能选择 $1$ 个关键审批节点，那么根节点 $1$ 必须被选中，否则根本自身无法被覆盖。

此时最深的节点 $5$ 到节点 $1$ 的距离为 $4$，因此答案为 $4$。