UiB Training 2017: Trees

Start

2017-11-15 15:15 UTC

UiB Training 2017: Trees

End

2017-11-22 15:15 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -396 days 2:04:53

Time elapsed

168:00:00

Time remaining

0:00:00

Problem C
Cat in a tree

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$, or the smell will be too overwhelming. Find the maximum number of nodes that the cat can mark.

Input

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 \leq N, D \leq 2 \cdot 10^5$.

Output

Output should contain one integer: the maximum number of nodes that can be marked.

Sample Input 1 Sample Output 1
4 3
0
0
1
2

Sample Input 2 Sample Output 2
3 1000
0
0
1