dlaud5379   1년 전

(Kagi Translate로 번역한 텍스트를 다듬었으며, 출력 지문 해석에 Claude의 도움을 받았습니다. 오역이 있으면 답글로 달아주세요. 감사합니다 🙇)

문제

S그룹의 상사-부하 관계는 트리 구조로 나타낼 수 있다. 즉, 사장을 제외한 모든 직원은 정확히 한 명의 직속 상사를 가진다. 또한, 각 직원들에게는 입사한 순서대로 사번이 매겨지며, 상사의 사번은 부하의 사번보다 항상 빠르다.

현재 S그룹 이사회에서는 조직에 사보타주 요원이 침투해 파업을 유도할 가능성을 우려하고 있으며, 파업이 확산되는 것을 막기 위해 상여금 지급, 운동회 개최, 탁구대 구매 등의 수단을 활용해 조직의 사기를 최대한 높게 유지하고자 한다. 조직의 사기 x는 0 이상 1 이하의 실수로, 만약 어떤 [역자 주: 부하 직원이 하나라도 있는] 직원 아래의 모든 직·간접 부하 직원 중 x를 초과하는 비율이 파업에 가담하게 된다면, 그 직원 역시 본인 아래의 모든 부하들을 데리고 파업에 가담할 것이다. 사보타주 요원은 직원 중 한 명이며, 잠복기를 거친 뒤 어느 순간 파업을 시작할 것이다(이때 본인의 부하를 동원하지는 않는다).

이사회에서는 파업에 가담하는 직원이 많아도 k명 이하가 되도록 하는 최소 사기를 구하고자 한다. 이 값을 계산하는 프로그램을 작성하여라.

입력

첫째 줄에 S그룹의 직원 수 n과 이사회에서 결정한 최대 파업 인원수 k가 공백으로 구분되어 주어진다. (1 ≤ k ≤ n ≤ 500,000)

다음 n-1줄에 걸쳐 조직 구조가 주어진다. i번째 줄에는 정수 pi (pi ≤ i)가 주어지며, 이는 i+1번 직원의 직속 상사가 pi번 직원이라는 의미이다. 이때 직원들의 사번은 1 이상 n 이하이며, 사장의 사번은 1이다.

출력

문제의 정답을 한 줄로 출력한다. 절대 오차가 10-6 이하이면 정답이다.

힌트

preview

사기가 2/3 미만으로 떨어질 경우, 사보타주 요원의 사번이 8번일 때 총 4명의 직원(3번, 7번, 8번, 9번)에 파업에 가담하게 된다.

댓글을 작성하려면 로그인해야 합니다.