사보타주
시간 제한2초메모리 제한1024 MB
직원 n명의 상사-부하 트리와 상한 k가 주어질 때, 어떤 직원이 반란을 시작하더라도 반란자가 k명 이하가 되는 가장 작은 사기 x를 구합니다.
문제
어떤 조직에서 상사와 부하 직원의 관계는 트리로 나타낼 수 있다. 사장을 제외한 모든 직원은 직속 상사가 정확히 한 명 있다. 직원에게는 입사 순서대로 번호가 붙고, 상사의 번호는 부하 직원의 번호보다 항상 작다.
이사회는 사보타주가 조직에 숨어들어 반란을 일으키려 한다고 우려한다. 이를 막기 위해 이사회는 직원들의 사기를 높게 유지하려 한다(예: 추가 보너스 지급, 사내 축제 개최, 탁구대 구입). 사기는 0에서 1 사이의 실수 x로 나타낸다. 어떤 직원이 자신의 직접 및 간접 부하 직원 중 x보다 큰 비율이 반란에 가담한 것을 알아차리면, 그 직원도 반란에 가담하고 모든 부하 직원을 반란에 끌어들인다. 사보타주는 직원 중 한 명이며, 어느 시점에 반란을 처음으로 일으켜 정체를 드러낸다. 다만 사보타주는 자신의 부하 직원을 반란에 끌어들이지 않는다.
이사회는 가능한 반란이 최대 k명의 직원에게만 미치도록 하려면 최소한 어느 정도의 사기를 유지해야 하는지 알고 싶어 한다. 이 값을 구하는 프로그램을 작성하라.
입력
첫 줄에 두 정수 n과 k (1 ≤ k ≤ n ≤ 500 000)가 공백으로 구분되어 주어진다. n은 직원 수이고, k는 반란에 참여할 수 있는 최대 인원이다. 직원은 1부터 n까지 번호가 붙어 있으며, 사장의 번호는 1이다. 이어지는 n − 1개의 줄 중 i번째 줄에는 정수 p_i (p_i ≤ i)가 주어지며, 이는 직원 i + 1의 직속 상사가 직원 p_i임을 뜻한다.
출력
필요한 사기를 나타내는 실수 하나를 출력한다. 정답과 차이가 10^{-6} 미만이면 정답으로 인정한다.
힌트
사기가 아래로 떨어지면, 사보타주가 8번 직원일 때 3, 7, 8, 9번 직원 4명의 반란이 일어난다.