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 1500$
• 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