← 返回题目列表

Codeforces · 1918/F

F. 树上的毛毛虫

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

毛毛虫决定访问树的每个节点。最初,它位于根部。

该树表示为有根树,根位于节点 $$$1$$$。毛毛虫每次爬行到相邻节点需要 $$$1$$$ 分钟。

树下有一个蹦床。如果毛毛虫从树上脱离并掉到蹦床上,它会在 $$$0$$$ 秒内到达树根。但蹦床很旧,只能承受 $$$k$$$ 毛毛虫的跌落。

毛毛虫访问树的所有节点所需的最短时间是多少?

更正式地说,如果毛毛虫从根(节点 $$$1$$$)开始并使用两种方法移动,我们需要找到访问树的所有节点所需的最短时间。

1. 沿着边缘爬行到相邻节点之一:需要 $$$1$$$ 分钟。
2.传送到根:不需要时间,不会访问新节点。

第二种方法(传送)最多可以使用 $$$k$$$ 次。毛毛虫可以在任意节点完成旅程。

输入

输入的第一行包含两个整数:$$$n$$$ ($$$2 \le n \le 2\cdot 10^5$$$) - 树中的节点数,$$$k$$$ ($$$0 \le k \le 10^9$$$) - 传送到根的最大数量。

第二行包含 $$$n-1$$$ 整数 $$$p_2$$$, $$$p_3$$$, ..., $$$p_n$$$ ($$$1 \le p_i \le n$$$) - 树中节点 $$$2, 3, \ldots, n$$$ 的祖先;节点 $$$1$$$ 是根节点。

输出

在一行中打印一个数字 - 访问树的所有节点所需的最少分钟数。

示例

输入 #1

8 1
1 1 2 2 4 3 3

输出 #1

9

输入 #2

4 0
4 4 1

输出 #2

4

注意

图中展示了从第一次测试开始9分钟遍历树的一种方式。