← 返回题目列表

Codeforces · 1065/F

F. 树上和下

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

给你一棵有 $$$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$$$,反之亦然。