Baltic Olympiad in Informatics: 2017 Day 2, Problem 3
A cat lives in a tree that has ~N~ nodes. She will demarcate her territory by marking some of the tree nodes. Marked nodes may not be closer to each other than distance ~D~. Find the maximum number of nodes that the cat can mark.
First line has two integers, ~N~ and ~D~. The ~0~th node is the root node of the tree. Then follows ~N-1~ lines, the ~i~th of which contain a single integer ~x_i~ with ~0 \leq x_i < i~ (starting with ~i= 1~). This means that node ~x_i~ is connected to node ~i~.
We always have ~1 \le N, D\le2\times 10^5~. For subcases, the inputs have these further restrictions:
- Group 1: 11 points ~N \le 18~
- Group 2: 40 points ~N \le 1\,500~
- Group 3: 49 points No further restrictions.
Output should contain one integer: the maximum number of nodes that can be marked.
Sample Input 1
4 3 0 0 1
Sample Output 1
Sample Input 2
3 1000 0 0
Sample Output 2