You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小猫在一棵有 $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

提示

数据范围与约定

本题采用捆绑测试。

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

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

说明

翻译自 BOI 2017 D2 T1 Cat in a tree。
翻译者：@一只书虫仔。