CF1918F Caterpillar on a Tree

毛毛虫决定访问树上的每一个节点。最初，它坐在根节点上。 这棵树表示为以 $1$ 号节点为根的有根树。每次爬到相邻的节点，毛毛虫需要 $1$ 分钟。 树下有一个蹦床。如果毛毛虫从树上跳下落到蹦床上，它会在 $0$ 秒内回到树的根节点。但蹦床很旧，最多只能承受 $k$ 次毛毛虫的跳跃。 毛毛虫访问完树上所有节点所需的最短时间是多少？ 更正式地说，我们需要求出毛毛虫从根节点（节点 $1$）出发，使用以下两种方式移动，访问所有节点所需的最短时间。 1. 沿树边爬到相邻节点：耗时 $1$ 分钟。 2. 传送回根节点：耗时 $0$ 分钟，且不会访问新的节点。 第二种方式（传送）最多只能使用 $k$ 次。毛毛虫可以在任意节点结束旅程。

输入的第一行包含两个整数：$n$（$2 \le n \le 2 \cdot 10^5$）——树的节点数，$k$（$0 \le k \le 10^9$）——最多允许传送回根节点的次数。 第二行包含 $n-1$ 个整数 $p_2, p_3, \ldots, p_n$（$1 \le p_i \le n$）——分别表示节点 $2, 3, \ldots, n$ 的父节点编号；节点 $1$ 是根节点。

输出一个整数，表示访问完所有节点所需的最短分钟数。

下图展示了第一个测试样例中用 9 分钟遍历整棵树的一种方式。  由 ChatGPT 4.1 翻译