ページが読み込まれませんか？ こちらをクリックすると直るかもしれません。
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
ログインしないとコードを書けません。