¿La página no carga? Prueba haciendo clic aquí.
Placeholder

#8157
Subtarea

강아지 영역표시 1s 512MB

Problemas

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

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


Entrada

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


Salida

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


Subtarea

# Puntaje Condición
#111

N \le 18

#240

N \le 1,500

#349

추가 제약 조건 없음


Ejemplo #1

4 3
0
0
1
2

Ejemplo #2

3 1000
0
0
1


Fuente

BOI 2017 D번

Debes iniciar sesión para escribir código.