[고등부] 2024 KOI 1차대회 대비 모의고사 (2주차)

트리에서 리프 노드란 자식이 없는 노드를 말한다.

N개의 노드로 이루어진 루트가 0이며 각 노드가 0부터 N-1번으로 번호가 매겨진 트리에서 K개의 노드를 제거하였을 때, 리프 노드의 최소 개수를 출력하는 프로그램을 작성하시오.

위 그림에서는 9개의 노드로 이루어진 트리에서 빨간색으로 표시된 노드들이 제거되었을 때, 초록색으로 표시된 두 개의 리프 노드가 존재하게 된다.

오직 루트 노드만이 남은 경우 루트 노드 또한 리프 노드로 간주하시오.

입력

첫 줄에 두 정수 N, K가 주어진다. (0 \le K < N \le 10^6)

이어 N-1줄에 걸쳐 i번째 줄에 i번 노드의 부모 노드의 번호를 의미하는 정수 P_i가 주어진다. (1 \le i < N, 0 \le P_i < i)

출력

첫 줄에 K개의 노드를 제거하였을 때 최소 리프 노드의 수를 출력한다.

부분문제

최소 리프 노드
서브태스크

4초 1024MB