P6574 [BalticOI 2017] Cat in a tree

A kitten is on a tree with $n$ nodes. It marks nodes to divide its territory. The nodes it marks must have pairwise distance at least $d$. The distance between two nodes is the number of edges on the path between them. Find the maximum number of nodes the kitten can mark.

The first line contains two integers: the number of nodes $n$ and the minimum required distance $d$ between marked nodes. Node $0$ is the root, and the nodes are numbered from $0$ to $n - 1$. The next $n - 1$ lines describe the edges. The $i$-th line contains one number $x_i$, meaning that node $i$ is connected to node $x_i$.

Output one integer: the maximum number of nodes the kitten can mark.

#### Constraints and Notes **This problem uses bundled testdata.** - Subtask 1 (11 pts): $n \le 18$. - Subtask 2 (40 pts): $n \le 1500$. - Subtask 3 (49 pts): no special constraints. For $100\%$ of the testdata, $1 \le n, d \le 2 \times 10^5$, $0 \le x_i < i$. #### Explanation **Translated from [BOI 2017 D2](https://boi.cses.fi/files/boi2017_day2.pdf) T1 Cat in a tree.** Translator: @[一只书虫仔](https://www.luogu.com.cn/user/114914)。 Translated by ChatGPT 5