给你一棵有 $$$n$$$ 个顶点的树;它的根是顶点$$$1$$$。还有一个令牌,最初放置在根中。您可以将标记移动到其他顶点。假设 token 的当前顶点是 $$$v$$$,那么你可以进行以下两种可能的移动:
- 向下移动到 $$$v$$$ 子树中的任何叶子;
- 如果顶点 $$$v$$$ 是叶子,则向上移动到父节点不超过 $$$k$$$ 次。换句话说,如果 $$$h(v)$$$ 是顶点 $$$v$$$ 的深度(根的深度是 $$$0$$$),那么您可以移动到顶点 $$$to$$$,使得 $$$to$$$ 是 $$$v$$$ 和 $$$h(v) - k \le h(to)$$$ 的祖先。
考虑根不是叶子(即使它的度是 $$$1$$$)。计算在一系列移动过程中您可以访问的不同叶子的最大数量。
输入
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k < n \le 10^6$$$) — 分别是树中的顶点数和向上移动的限制。
第二行包含 $$$n - 1$$$ 整数 $$$p_2, p_3, \dots, p_n$$$,其中 $$$p_i$$$ 是顶点 $$$i$$$ 的父节点。
保证输入代表一棵有效的树,根部为 $$$1$$$。
输出
打印一个整数 — 您可以访问的不同叶子的最大可能数量。
示例
输入 #1
7 1 1 1 3 3 4 4
输出 #1
4
输入 #2
8 2 1 1 2 3 4 5 5
输出 #2
2
注意
第一个示例的图表:
最佳方法之一是下一种:$$$1 \rightarrow 2 \rightarrow 1 \rightarrow 5 \rightarrow 3 \rightarrow 7 \rightarrow 4 \rightarrow 6$$$。
第二个示例的图表:
最佳方法之一是下一种:$$$1 \rightarrow 7 \rightarrow 5 \rightarrow 8$$$。请注意,无法从 $$$6$$$ 移动到 $$$7$$$ 或 $$$8$$$,反之亦然。