시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 (추가 시간 없음) | 1024 MB | 108 | 22 | 18 | 17.647% |
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 yi feet. One of the tree leaves contains the motherlode, and each other ore pocket contains xi 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 yi 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:
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:
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 xi in each pocket and length yi 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 pi, xi, and yi encoding information about the ith node of the tree. pi (0 ≤ pi < 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). xi is the value of the ore in node i, and yi (1 ≤ yi ≤ 1 000) is the length of the tunnel connecting node pi to node i. Exactly one node has xi = −1, indicating that the node contains the motherlode; all other inputs satisfy 0 ≤ xi ≤ 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.
5 0 3 1 0 0 2 2 -1 1 2 0 5
8 1
5 0 -1 4 0 2 1 0 4 3 0 3 2
7 1
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.
ICPC > Regionals > North America > North America Qualification Contest > ICPC North America Qualifier 2019 F번