题目描述

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 completely-excavated 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.

Given the mine layout, compute $a$ and $b$.

Figure 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 \leq n \leq 200\, 000$), the number of nodes in the tree representing Pete’s mine. The remaining input consists of $n-1$ lines, the $i$th of which (starting at $1$) contains three integers $p_ i$, $x_ i$, and $y_ i$ encoding information about the $i$th node of the tree. $p_ i$ ($0 \le p_ i \le i$) is the index of the $i$th 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 \leq y_ i \leq 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 \leq x_ i \leq 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.

样例

输入样例1

5
0 3 1
0 0 2
2 -1 1
2 0 5

输出样例1

8 1

输入样例2

5
0 -1 4
0 2 1
0 4 3
0 3 2

输出样例2

7 1

数据范围与提示

Consider the mine described in sample input 1 and illustrated in Figure 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 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.