17590번 - Prospecting 다국어

Prospectin’ Pete has a lead on a new titanium mine, and needs your help pitching a mining operation to investors. The mine can be represented as a tree: the mine entrance is the root of the tree, other tree nodes are pockets of underground titanium ore, and the tree edges are potential tunnels Pete can dig between two pockets (or between the mine entrance and one pocket, for edges adjacent to the root node). The tunnel connecting the i-th ore pocket to its parent has a length of y_i feet. One of the tree leaves contains the motherlode, and each other ore pocket contains x_i dollars worth of ore.

Pete begins at the mine entrance, and his goal is to reach the motherlode. Obviously, Pete cannot travel to pocket i until all y_i feet of dirt in the tunnel leading to it has been removed. But once a tunnel has been completely excavated, Pete can travel that tunnel, in both directions, as many times as he wants.

Pete explores the mines by repeatedly performing the following steps, in order:

1. Pete chooses a tunnel that he can reach from his current location, and that has not yet been fully excavated.
2. Pete digs through one foot of the chosen tunnel; this costs him one dollar.
3. If the tunnel is now completely clear, Pete travels through the tunnel to the newly opened pocket and mines the ore. If that pocket contains the motherlode, then he stops exploring the mine. Otherwise, he sells the ore in that pocket for x_i dollars and continues exploring.

Note that the tunnel Pete chooses to dig in the first step of each round of digging does not need to be adjacent to his current location, so long as Pete can reach the tunnel by traveling through the mine along a sequence of completelyexcavated tunnels. He can also choose a different tunnel each round, even if the tunnel he was digging in the previous round is not yet completely excavated. If Pete ends a round of digging with no money, and without having reached the motherlode, the mining operation is a bust and Pete goes home bankrupt.

Pete has surveyed the geology of the area and knows the mine layout, as well as the amount of ore in each chamber, but hasn’t yet decided on a strategy for how to dig the tunnels. He knows that in addition to any riches he earns from the mine itself, he will need some amount of startup money in order to reach the motherlode, and so he is courting investors. He wants to present them with two pieces of information:

• The minimum number of dollars a that Pete must begin with in order for his venture to be successful even in the worst-case: for it to be guaranteed that he reaches the motherlode no matter how he chooses the tunnel to excavate during each round of digging.
• The minimum number of dollars b that Pete must begin with in order to reach the motherlode in the best-case scenario where Pete chooses tunnels optimally.

This information will allow the investors to decide how much to fund Pete, based on how much they trust him to dig optimally without making any mistakes.

Given the mine layout, compute a and b.

Figure F.1: Illustrations of sample inputs 1 (on the left) and 2. Edges represent tunnels and nodes represent ore pockets. Ore values x_i in each pocket and length y_i of each tunnel are written in black text (“ML” stands for the motherlode). Nodes are labeled in red with their indices.

The first line of input contains an integer n (2 ≤ n ≤ 200 000), the number of nodes in the tree representing Pete’s mine. The remaining input consists of n − 1 lines, the ith of which (starting at 1) contains three integers p_i, x_i, and y_i encoding information about the ith node of the tree. p_i (0 ≤ p_i < i) is the index of the ith node’s parent in the tree. A parent index of zero means that the node’s parent is the mine entrance (root of the tree). x_i is the value of the ore in node i, and y_i (1 ≤ y_i ≤ 1 000) is the length of the tunnel connecting node p_i to node i. Exactly one node has x_i = −1, indicating that the node contains the motherlode; all other inputs satisfy 0 ≤ x_i ≤ 1 000.

Note that node zero is the mine entrance; it contains no ore and has no corresponding line in the input. You may assume that the motherlode is a leaf of the tree (no node has the motherlode node as a parent).

Print two space-separated integers a and b, the worst-case and best-case investment Pete needs in order to clear a path to the motherlode, as described in more detail above.

Consider the mine described in sample input 1 and illustrated in Figure F.1. Pete needs 8 dollars to guarantee he reaches the motherlode even with poor digging choices: in the worst-case scenario he spends 2 dollars to completely clear the tunnel leading into pocket 2, and then 5 more dollars to clear the tunnel leading to pocket 4. With his last dollar he either digs his way to the motherlode, or opens the tunnel to pocket 1, which gives him enough money to reach the motherlode in the next round of digging. In the best-case scenario he needs only one dollar: he spends that dollar to first dig through the tunnel leading into pocket 1, and with the 3 dollars of ore he mines there, he can dig through the two tunnels on the path from the entrance to the motherlode.

A second example is provided in sample input 2 which is also illustrated in Figure F.1. In one worst-case scenario, Pete excavates three feet of the tunnel leading to pocket 1, two feet of the tunnel leading to pocket 3, and one foot of the tunnel leading to pocket 4, all without mining any ore. This costs him 6 dollars. With a seventh dollar, Pete is guaranteed to tunnel into an ore pocket which finances exploration of the rest of the mine (including the motherlode). In the best-case scenario, Pete needs only a single dollar: he first digs to pocket 2, then 4, then 3, then 1, finding the motherlode.