8184: USACO 2023 February Contest, Gold Problem 2. Fertilizing Pastures
[Creator : ]
Description
There are N pastures $(2≤N≤2⋅10^5)$, 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 i-th pasture's grass grows at a rate of $a_i\ (1≤ai≤10^8)$ 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}.
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.
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$, meaning that there is a road connecting pastures $p_i$ and i. It is guaranteed that $1≤p_i<i$.
Output
The minimum amount of time and the minimum amount of fertilizer, separated by spaces.
Sample 1 Input
5 0
1 1
1 2
3 1
3 4
Sample 1 Output
8 21
The optimal route for Farmer John is as follows:
- At time 1, move to node 3, which now has 1⋅2=2 grass and so needs 2 fertilizer.
- At time 2, move to node 5, which now has 2⋅4=8 grass and so needs 8 fertilizer.
- At time 3, move back to node 3, which we already fertilized and so don't need to fertilize again.
- At time 4, move to node 4, which now has 4⋅1=4 grass and so needs 4 fertilizer.
- At time 5, move back to node 3, which we already fertilized.
- At time 6, move back to node 1.
- At time 7, move to node 2, which now has 7⋅1=7 grass and so needs 7 fertilizer.
- At time 8, return to node 1.
Sample 2 Input
5 1
1 1
1 2
3 1
3 4
Sample 2 Output
6 29
The optimal route for Farmer John is as follows:
- At time 1, move to node 2, which now has 1⋅1=1 grass and so needs 1 fertilizer.
- At time 2, move back to node 1.
- At time 3, move to node 3, which now has 3⋅2=6 grass and so needs 6 fertilizer.
- At time 4, move to node 5, which now has 4⋅4=16 grass and so needs 16 fertilizer.
- At time 5, move back to node 3, which we already fertilized and so don't need to fertilize again.
- At time 6, move to node 4, which now has 6⋅1=6 grass and so needs 6 fertilizer.