頁面無法載入？點擊這裡可能會修復。
Placeholder

#2143

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

최소 리프 노드
子任務
4秒 1024MB

問題

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

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개의 노드를 제거하였을 때 최소 리프 노드의 수를 출력한다.


子任務

編號 分數 條件
#110分

K \in \{0, N-1\}. 즉, K는 0 또는 N-1이다.

#230分

N < 10

#360分

추가 제한 없음


範例 #1

5 2
0
0
1
1
1

範例 #2

9 3
0
0
1
1
1
4
5
6
2
需要登入才能撰寫程式碼。