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.

Input Specification

First line has two integers, ~N~ and ~D~. The ~0^\text{th}~ node is the root node of the tree. Then follows ~N-1~ lines, the ~i^\text{th}~ of which contain a single integer ~x_i~ with ~0 \le x_i < i~ (starting with ~i=1~). This means that node ~x_i~ is connected to node ~i~.

Constraints

We always have ~1 \le N, D \le 2 \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 Specification

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

2

Sample Input 2

3 1000
0
0

Sample Output 2

1