페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8157
서브태스크

강아지 영역표시 1초 512MB

문제

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

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


입력

첫 줄에 두 정수 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


출력

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


부분문제

번호 점수 조건
#111점

N \le 18

#240점

N \le 1,500

#349점

추가 제약 조건 없음


예제1

입력
43
0
0
1
출력
2

예제2

입력
31000
0
0
출력
1

태그

출처

BOI 2017 D번

역링크