시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB135331616.495%

문제

사람의 신체는 안전하고 위험한 음식을 구별할 수 있는 방법이 필요하다. 인간의 혀는 대표적으로 네 가지 유형의 맛을 감지할 수 있는데 단맛, 신맛, 쓴맛, 짠맛이 그것이다. 우리가 흔히 말하는 맛있다, 맛없다의 맛에 관한 호불호는 이러한 단맛, 신맛, 쓴맛, 짠맛의 조합과 개인 기호에 기반한다.

하지만 준표는 맛을 느낄 수 없다. 신김치를 먹고 시지 않다고 말하는 준표를 보고 이를 알아챈 서현이는 준표가 위험한 맛들을 감지하지 못해 사고가 날까봐 걱정이 되었다. 서현이는 왜 준표가 맛을 느끼지 못하는지, 그리고 왜 자신의 미각이 정상이 아님을 인정하지 못하는지 조사하기 시작했고, 준표에게 1 ~ N 번으로 번호가 붙여진 N 개의 미뢰가 존재하는 것을 알아냈다.

놀랍게도 준표의 미뢰들은 서로간의 연결관계를 통해 1번 미뢰를 루트로 하는 하나의 이진 트리의 형태로 이루어져 있다. 하나의 트리는 하나의 미뢰집단이다. 일반적인 사람들은 X 개 이상의 미뢰집단을 가지고 있다. 또한 맛이란 복합적인 것이기 때문에 각 미뢰집단은 적어도 K 개 이상의 미뢰로 구성되어 있어야 제대로 된 역할을 할 수 있다. 서현이는 준표의 미뢰들 사이에 존재하는 연결관계를 끊어 준표가 일반사람들과 같이 K 개 이상의 미뢰로 구성된 미뢰집단을 X 개 이상 가지게 하고싶다.

하지만 연결관계를 끊을때마다 그 연결관계의 세기만큼 준표의 다른 신경계가 손상을 입을 수 있다. A와 B 미뢰 사이의 연결이 서로에게 10만큼의 영향을 주고 있다면, 이 연결관계를 끊었을때 준표도 10만큼의 고통을 받게 되는 것이다. 미각이 돌아와도 다른 감각이 상처를 입으면 준표가 더더욱 힘든 삶을 살게 될 것이므로, 서현이는 끊어야하는 연결의 영향의 합, 즉 준표가 받을 고통의 합을 최소로 하고 싶다. 이때 준표가 다시 맛을 느끼기 위해서 받게될 최소 고통의 합은 얼마일지 알아보자.

입력

첫 줄에 준표가 가진 미뢰의 개수 N(1 ≤ N ≤ 5,000), 한 미뢰집단이 정상적인 동작을 위해 가져야하는 최소 미뢰의 수 K(1 ≤ K ≤ 100), 보통사람처럼 맛을 느끼기 위해서 필요한 최소 정상 미뢰집단의 수 X(1 ≤ X ≤ 100) 가 주어진다.

이후 N-1개 줄에 걸쳐 i(2 ≤ i ≤ N)번 미뢰의 정보 Pi (1 ≤ Pi ≤ N), Ci (0 ≤ Ci ≤ 100,000) 가 주어진다. 이는 i번 미뢰의 부모가 Pi 번 미뢰이며, 이 둘 사이를 끊게 되면 Ci만큼의 고통이 발생함을 의미한다. 1번 미뢰는 루트이므로 정보가 들어오지 않는다.

출력

준표가 다시 맛을 느끼기 위해 겪어야하는 고통의 합의 최솟값을 출력한다. 만약 준표가 어떻게 해도 미각을 되찾을 수 없는 상태라면 -1을 출력한다.

예제 입력 1

3 1 3
1 4
1 3

예제 출력 1

7

예제 입력 2

7 3 2
1 5
2 6
2 7
3 4
4 2
4 1

예제 출력 2

7

힌트

2번 예제에서 2번 미뢰와 4번 미뢰 사이의 연결을 끊는 것이 고통의 합이 최소가 된다.

출처

University > 경인지역 6개대학 연합 > shake! 2017 F번

  • 문제를 만든 사람: Acka