광 통신 채널

시간 제한1초메모리 제한512 MB

요약

루트가 있는 트리에서 각 정점에 연결되는 간선이 최대 k개가 되도록 간선을 고릅니다. 간선 수를 최대로 하고, 그중 가중치 합이 최소인 선택을 구합니다.

난이도: 어려움10점 중 8점
유형: 트리, 동적 계획법, 그리디
정답자: 아직 제출이 없습니다

문제

플랫랜드에는 $n$ 개의 도시가 있고, 1부터 $n$ 까지 번호가 붙어 있다. 수도는 1번 도시이다. 플랫랜드의 컴퓨터 네트워크는 다음과 같이 구성되어 있다. 각 도시에는 연결 센터가 하나씩 있고, 이 센터는 유선 통신 채널로 다른 센터들과 연결될 수 있다. 임의의 두 도시 사이에는 채널을 따라가는 경로가 정확히 하나 있다. 즉, 네트워크는 트리이다. $i > 1$ 인 도시 $i$ 에 대해, 도시 $i$ 에서 수도까지 가는 경로에서 처음 만나는 도시를 $p_i$ 라고 한다.

네트워크 현대화 작업이 진행되며, 일부 유선 채널이 더 새로운 광 채널로 교체된다. 광 채널은 기존 유선 채널 자리에만 설치할 수 있다. 도시 $i$ 와 도시 $p_i$ 를 잇는 채널을 교체하는 비용은 $w_i$ 이다. 기술적 제약으로 인해 어떤 연결 센터도 광 채널로 최대 $k$ 개의 다른 센터와만 연결될 수 있다.

플랫랜드 통신부는 현대화 후 광 채널 네트워크의 연결성이 가능한 한 높아지도록 교체 계획을 세우려 한다. 따라서 교체할 채널을 가능한 한 많이 골라야 한다. 교체 채널 수가 같다면 교체 비용의 합이 최소인 계획을 골라야 한다.

통신부 담당자들이 교체할 채널을 고를 수 있도록 도와라.

입력

첫 줄에 두 정수 $n$ 과 $k$ 가 주어진다( $2 \le n \le 10^5$ , $1 \le k \le 100$ ). 다음 $n - 1$ 개 줄에는 두 정수 $p_i$ 와 $w_i$ 가 주어진다( $1 \le p_i \le i$ , $0 \le w_i \le 10^9$ ). $(i-1)$ 번째 줄은 도시 $i$ 에 대한 설명이다.

출력

두 정수 $cnt$ 와 $cost$ 를 출력한다. $cnt$ 는 교체할 수 있는 채널의 최대 개수이고, $cost$ 는 그 개수만큼 채널을 교체할 때의 최소 비용이다.

힌트

첫 번째 예제에서 현대화 전후의 네트워크 구성은 아래 그림과 같다. 굵은 선은 교체할 채널이다. 교체할 수 있는 채널의 최대 개수는 4이다. 모든 채널의 교체 비용은 0이므로 그림에는 표시하지 않았다.

채널 4개를 교체하는 다른 해도 존재한다.

두 번째 예제의 현대화 전후 구성은 아래 그림과 같다. 굵은 선이 교체할 채널이고, 채널 옆에는 교체 비용이 적혀 있다. 교체할 수 있는 채널의 최대 개수는 6이고, 최적 해의 총 비용은 27이다.

예제2

예제 1
입력
```
8 2
1 0
1 0
1 0
2 0
2 0
2 0
1 0
```
예상 출력
```
4 0
```
예제 2
입력
```
8 3
1 5
1 2
1 4
2 6
2 7
2 2
1 6
```
예상 출력
```
6 27
```