문제
There are N pastures (2≤N≤2⋅105), connected by N−1 roads, such that they form a tree.
Every road takes 1 second to cross. Each pasture starts out with 0 grass, and the ith pasture's grass grows at a rate of ai (1≤ai≤108) units per second.
Farmer John is in pasture 1 at the start, and needs to drive around and fertilize the grass in every pasture.
If he visits a pasture with x units of grass, it will need x amount of fertilizer.
A pasture only needs to be fertilized the first time it is visited, and fertilizing a pasture takes 0 time.
The input contains an additional parameter T∈{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 amount of time it will take to fertilize every pasture and the minimum amount of fertilizer needed to finish in that amount of time.
입력
The first line contains N and T.
Then for each i from 2 to N, there is a line containing pi and ai, meaning that there is a road connecting pastures pi and i.
It is guaranteed that 1≤pi<i.
출력
The minimum amount of time and the minimum amount of fertilizer, separated by spaces.
예제 #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
로그인해야 코드를 작성할 수 있어요.