Description

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.

Input Format

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 Format

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

4 3
0
0
1

2

3 1000
0
0

1

Hint

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 T1 Cat in a tree.
Translator: @一只书虫仔。

Translated by ChatGPT 5