목초지에 비료 주기

시간 제한2초메모리 제한1024 MB

요약

1번 목장에서 출발해 트리의 모든 목장을 한 번씩 방문하며, 목장마다 초당 a_i만큼 자라는 풀에 줄 비료의 최소 시간과 최소 양을 구합니다.

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

문제

목초지 $N$ 개( $2 \le N \le 2\cdot 10^5$ )가 $N-1$ 개의 도로로 연결되어 있고, 이 도로들은 트리를 이룬다. 각 도로를 건너는 데 1초가 걸린다. 모든 목초지의 풀은 처음에 0이며, $i$ 번 목초지의 풀은 초당 $a_i$ ( $1\le a_i\le 10^8$ ) 단위씩 자란다. 농부 존은 1번 목초지에서 출발해서 차를 몰고 다니며 모든 목초지에 비료를 줘야 한다. 풀이 $x$ 단위 자란 목초지를 방문하면 $x$ 단위의 비료가 필요하다. 목초지는 처음 방문할 때만 비료를 주면 되고, 비료를 주는 데는 시간이 걸리지 않는다.

입력에는 추가 매개변수 $T\in \{0,1\}$ 이 주어진다.

$T=0$ 이면 존은 1번 목초지에서 끝나야 한다.
$T=1$ 이면 존은 어느 목초지에서 끝나도 된다.

모든 목초지에 비료를 주는 데 걸리는 최소 시간과, 그 시간 안에 끝내는 데 필요한 비료의 최소량을 구하라.

입력

첫 줄에 $N$ 과 $T$ 가 주어진다. 이후 $i$ 가 $2$ 부터 $N$ 까지인 각 줄에는 $p_i$ 와 $a_i$ 가 주어지며, 이는 목초지 $p_i$ 와 $i$ 를 잇는 도로가 있다는 뜻이다. $1\le p_i<i$ 가 보장된다.

출력

최소 시간과 최소 비료량을 공백으로 구분하여 출력한다.

예제2

예제 1
입력
```
5 0
1 1
1 2
3 1
3 4
```
예상 출력
```
8 21
```
예제 2
입력
```
5 1
1 1
1 2
3 1
3 4
```
예상 출력
```
6 29
```