Fertilizing Pastures

Time limit2sMemory limit1024 MB

Summary

Walk a tree from pasture 1 to visit every pasture, where grass grows at rate a_i, and report the minimum time and the least fertilizer for that time.

Level: Hard8 of 10
Topics: Tree, DFS, Greedy, Sorting
Solved: No attempts yet

Statement

There are $N$ pastures ( $2 \le N \le 2\cdot 10^5$ ), connected by $N-1$ roads so that they form a tree. Each road takes 1 second to cross. Every pasture starts with 0 grass, and the grass in pasture $i$ grows at $a_i$ ( $1\le a_i\le 10^8$ ) units per second. Farmer John starts in pasture 1 and must drive around to fertilize the grass in every pasture. If he visits a pasture with $x$ units of grass, it needs $x$ units of fertilizer. A pasture only needs fertilizer the first time it is visited, and fertilizing takes no time.

The input has an extra parameter $T\in \{0,1\}$ .

If $T=0$ , Farmer John must end at pasture 1.
If $T=1$ , Farmer John may end at any pasture.

Compute the minimum time to fertilize every pasture, and the minimum amount of fertilizer needed to finish in that time.

Input

The first line contains $N$ and $T$ . Then for each $i$ from $2$ to $N$ , there is a line containing $p_i$ and $a_i$ , which means a road connects pastures $p_i$ and $i$ . It is guaranteed that $1\le p_i<i$ .

Output

Print the minimum time and the minimum fertilizer, separated by a space.

Examples2

Example 1
Input
```
5 0
1 1
1 2
3 1
3 4
```
Expected output
```
8 21
```
Example 2
Input
```
5 1
1 1
1 2
3 1
3 4
```
Expected output
```
6 29
```