잎 줄이기

베네룩스 고급 전화 회사(BAPC)는 베네룩스 지역에서 가장 큰 전화망을 보유하고 있다. 안타깝게도 네트워크가 너무 커져서 제대로 관리하기 어렵다. 그래서 BAPC는 네트워크 일부를 매각하기로 했다.

네트워크는 서로 연결된 전송 노드로 구성된다. 노드 하나는 중앙 교환기로 지정된다. 나머지 모든 노드는 상위 전송 노드가 정확히 하나씩 있다. 어느 노드에서든 상위 연결을 따라 올라가면 결국 중앙 교환기에 도달한다. 하위 노드가 없는 노드를 잎 노드, 즉 고객 전송 노드라고 한다.

매각할 때는 무결성을 유지해야 한다. BAPC가 노드 $X$를 매각하면, $X$의 하위에 있는 모든 노드도 함께 매각해야 한다.

BAPC는 정확히 $k$개의 전송 노드를 매각한다. 이 $k$개를 고르는 방법은 여러 가지가 있다. BAPC는 관리를 최대한 편하게 하고 싶어 하므로, 무결성을 지키면서 매각 후 네트워크에 남는 고객 전송 노드의 수를 최소로 만들려고 한다.

예를 들어 그림 L.1에 나온 두 번째 입력 사례를 보자. 빨간 줄무늬 노드 세 개가 매각되고, 굵은 초록색 노드 두 개가 남은 고객 노드이다.

그림 L.1: 두 번째 입력 사례의 시각화.

입력은 다음과 같이 주어진다.

• 첫 줄에 두 정수 $n$과 $k$가 주어진다($0\leq k < n\leq 10^6$). $n$은 전송 노드의 수이고, $k$는 매각할 노드의 수이다.
• 이어서 $n-1$개의 줄이 주어진다. $i$번째 줄에는 정수 $p_i$($0 \leq p_i < i$) 하나가 주어지며, 이는 전송 노드 $i$($1 \leq i < n$)가 노드 $p_i$로 나가는 연결을 가진다는 뜻이다.

전송 노드에는 $0$부터 $n-1$까지 번호가 붙는다. 노드 $0$은 항상 중앙 교환기이다.

$k$개의 전송 노드를 매각한 뒤 남는 고객 전송 노드의 최소 개수를 출력한다. 중앙 교환기만 남으면 그것도 고객 노드로 센다.