Cat in a tree

시간 제한1초메모리 제한512 MB

요약

N개 노드로 이루어진 루트 트리에서 임의의 두 노드 사이 거리가 D 이상이 되도록 고를 수 있는 노드 수의 최댓값을 구한다.

난이도: 보통10점 중 7점
유형: 트리, 그리디, DFS, 동적 계획법
정답자: 아직 제출이 없습니다

문제

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 xi with 0 ≤ xi < i (starting with i = 1). This means that node xi is connected to node i.

출력

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

제한

We always have 1 ≤ N, D ≤ 2 · 105. For subcases, the inputs have these further restrictions.

예제2

예제 1
입력
```
4 3
0
0
1
```
예상 출력
```
2
```
예제 2
입력
```
3 1000
0
0
```
예상 출력
```
1
```