题目描述

题目译自 BalticOI 2017 Day2「Cat in a tree」

小猫在一棵有 $n$ 个节点的树上，它通过标记节点来划分领地。
它标记的节点满足彼此距离不小于 $d$。
两节点之间的距离指的是两点间路径上的边数。
求小猫最多能标记多少个节点。

输入格式

第一行两个整数代表节点数 $n$ 和标记的节点不超过的距离 $d$。
第 $0$ 个节点就是根节点，节点的编号为从 $0$ 到 $n - 1$。
接下来 $n-1$ 行，第 $i$ 行代表第 $i$ 个节点与哪个节点相连，一个数 $x_i$ 代表编号为 $i$ 的节点与编号为 $x_i$ 的节点相连。

输出格式

一行一个整数代表猫最多能标记多少个节点。

4 3
0
0
1

2

3 1000
0
0

1

数据范围与提示

对于 $100\%$ 的数据，$1 \le n,d \le 2 \times 10^5$，$0 \le x_i < i$。

详细子任务与附加限制如下：

• Subtask 1（11 pts）：$n \le 18$。
• Subtask 2（40 pts）：$n \le 1500$。
• Subtask 3（49 pts）：无特殊限制。