비료 주기

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

📃 해결할 문제

$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\lti$ 이 보장됩니다.

🖨️ 출력

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

💻 예제 입력 1

🖨️ 예제 출력 1

8 21

💻 예제 입력 2

🖨️ 예제 출력 2

6 29

💡 힌트

입력 예사:

출력 예사:

6 29

현우의 최적 경로는 다음과 같습니다:

시간 $1$ 에서, 노드 $3$ 으로 이동하면, 그곳에는 이제 $1 \cdot 2 = 2$ 풀이 있으므로 $2$ 비료가 필요하다.
시간 $2$ 에서, 노드 $5$ 로 이동하면, 그곳에는 이제 $2 \cdot 4 = 8$ 풀이 있으므로 $8$ 비료가 필요하다.
시간 $3$ 에서, 다시 노드 $3$ 으로 이동하면, 이미 비료를 줬기 때문에 다시 비료를 줄 필요가 없다.
시간 $4$ 에서, 노드 $4$ 로 이동하면, 그곳에는 이제 $4 \cdot 1 = 4$ 풀이 있으므로 $4$ 비료가 필요하다.
시간 $5$ 에서, 다시 노드 $3$ 으로 이동하면, 이미 비료를 줬기 때문에 다시 비료를 줄 필요가 없다.
시간 $6$ 에서, 다시 노드 $1$ 로 이동하다.
시간 $7$ 에서, 노드 $2$ 로 이동하면, 그곳에는 이제 $7 \cdot 1 = 7$ 풀이 있으므로 $7$ 비료가 필요하다.
시간 $8$ 에서, 다시 노드 $1$ 로 돌아온다.

이 경로는 $8$ 의 시간이 걸리며 $2 + 8 + 4 + 7 = 21$ 의 비료를 사용합니다. 노드 $1$ 로 돌아가는 어떤 경로의 경우 $8$ 은 최소한의 시간이며 $21$ 은 $8$ 의 시간이 걸리는 어떤 경로의 경우 최소한의 비료 사용량입니다.

점수:

입력 3-10: $T=0$
입력 11-22: $T=1$
입력 3-6와 11-14: 목장 하나가 세 개 이상의 도로와 인접해있지 않다.

출처: USACO 2023 February Contest, Gold Problem 2. Fertilizing Pastures