Page not loading? Try clicking here.
Placeholder

#8157
Subtask

강아지 영역표시 1s 512MB

Problems

강아지 한 마리가 N개의 노드로 이루어진 트리에서 살고 있다. 강아지는 트리의 일부 노드에 영역표시를 할 수 있는데, 영역표시가 된 노드 사이의 거리는 D 보다 가까워서는 안된다.

과연 강아지는 최대 몇 개의 노드에 영역표시를 하는 것이 가능할지 알아보자.


Input

첫 줄에 두 정수 N과 D가 주어진다.

두 번째 줄부터 N-1 줄에 걸쳐 각 i번째 줄에 i번 노드가 연결된 노드의 번호를 의미하는 정수 x_i가 주어진다. (0 \le x_i < i ; 1 \le i \le N)

[제약 조건]

  • 1 \le N \le 2 \cdot 10^5

  • 1 \le D \le 2 \cdot 10^5


Output

첫 줄에 강아지가 영역표시 할 수 있는 최대 노드의 수를 출력한다.


Subtask

# Score Condition
#111

N \le 18

#240

N \le 1,500

#349

추가 제약 조건 없음


Example #1

4 3
0
0
1
2

Example #2

3 1000
0
0
1


Source

BOI 2017 D번

You must sign in to write code.