毛毛虫决定访问树的每个节点。最初,它位于根部。
该树表示为有根树,根位于节点 $$$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分钟遍历树的一种方式。