{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cp\u003eProspectin’ Pete has a lead on a new titanium mine, and\n needs your help pitching a mining operation to investors. The\n mine can be represented as a tree: the mine entrance is the\n root of the tree, other tree nodes are pockets of underground\n titanium ore, and the tree edges are potential tunnels Pete can\n dig between two pockets (or between the mine entrance and one\n pocket, for edges adjacent to the root node). The tunnel\n connecting the \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e-th ore\n pocket to its parent has a length of \u003cspan class\u003d\"tex2jax_process\"\u003e$y_ i$\u003c/span\u003e feet. One of the tree leaves\n contains the motherlode, and each other ore pocket contains\n \u003cspan class\u003d\"tex2jax_process\"\u003e$x_ i$\u003c/span\u003e dollars worth of\n ore.\u003c/p\u003e\n \u003cp\u003ePete begins at the mine entrance, and his goal is to reach\n the motherlode. Obviously, Pete cannot travel to pocket\n \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e until all \u003cspan class\u003d\"tex2jax_process\"\u003e$y_ i$\u003c/span\u003e feet of dirt in the tunnel\n leading to it has been removed. But once a tunnel has been\n completely excavated, Pete can travel that tunnel, in both\n directions, as many times as he wants.\u003c/p\u003e\n \u003cp\u003ePete explores the mines by repeatedly performing the\n following steps, in order:\u003c/p\u003e\n \u003col class\u003d\"enumerate\"\u003e\n \u003cli\u003e\n \u003cp\u003ePete chooses a tunnel that he can reach from his current\n location, and that has not yet been fully excavated.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003ePete digs through one foot of the chosen tunnel; this\n costs him one dollar.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eIf the tunnel is now completely clear, Pete travels\n through the tunnel to the newly opened pocket and mines the\n ore. If that pocket contains the motherlode, then he stops\n exploring the mine. Otherwise, he sells the ore in that\n pocket for \u003cspan class\u003d\"tex2jax_process\"\u003e$x_ i$\u003c/span\u003e\n dollars and continues exploring.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ol\u003e\n \u003cp\u003eNote that the tunnel Pete chooses to dig in the first step\n of each round of digging does not need to be adjacent to his\n current location, so long as Pete can reach the tunnel by\n traveling through the mine along a sequence of\n completely-excavated tunnels. He can also choose a different\n tunnel each round, even if the tunnel he was digging in the\n previous round is not yet completely excavated. If Pete ends a\n round of digging with no money, and without having reached the\n motherlode, the mining operation is a bust and Pete goes home\n bankrupt.\u003c/p\u003e\n \u003cp\u003ePete has surveyed the geology of the area and knows the mine\n layout, as well as the amount of ore in each chamber, but\n hasn’t yet decided on a strategy for how to dig the tunnels. He\n knows that in addition to any riches he earns from the mine\n itself, he will need some amount of startup money in order to\n reach the motherlode, and so he is courting investors. He wants\n to present them with two pieces of information:\u003c/p\u003e\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eThe minimum number of dollars \u003cspan class\u003d\"tex2jax_process\"\u003e$a$\u003c/span\u003e that Pete must begin with in\n order for his venture to be successful even in the\n worst-case: for it to be guaranteed that he reaches the\n motherlode no matter how he chooses the tunnel to excavate\n during each round of digging.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eThe minimum number of dollars \u003cspan class\u003d\"tex2jax_process\"\u003e$b$\u003c/span\u003e that Pete must begin with in\n order to reach the motherlode in the best-case scenario\n where Pete chooses tunnels optimally.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n \u003cp\u003eThis information will allow the investors to decide how much\n to fund Pete, based on how much they trust him to dig optimally\n without making any mistakes.\u003c/p\u003e\n \u003cp\u003eGiven the mine layout, compute \u003cspan class\u003d\"tex2jax_process\"\u003e$a$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$b$\u003c/span\u003e.\u003c/p\u003e\n \u003cdiv id\u003d\"fig:prospecting\" class\u003d\"figure\"\u003e\n \u003ccenter\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/d4a771c3c70726d6fe01431aae71c3af?v\u003d1715772388\" alt\u003d\"\\includegraphics[width\u003d0.7\\textwidth ]{prospecting_sample}\" style\u003d\"width:70.00%\"\u003e\n \u003cdiv class\u003d\"caption\"\u003e\n \u003cb\u003eFigure 1\u003c/b\u003e: Illustrations of sample inputs\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e (on the left)\n and \u003cspan class\u003d\"tex2jax_process\"\u003e$2$\u003c/span\u003e. Edges\n represent tunnels and nodes represent ore pockets. Ore\n values \u003cspan class\u003d\"tex2jax_process\"\u003e$x_ i$\u003c/span\u003e in\n each pocket and length \u003cspan class\u003d\"tex2jax_process\"\u003e$y_\n i$\u003c/span\u003e of each tunnel are written in black text (“ML”\n stands for the motherlode). Nodes are labeled in red with\n their indices.\n \u003c/div\u003e\n \u003c/center\u003e\n \u003c/div\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eThe first line of input contains an integer \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$2\n \\leq n \\leq 200\\, 000$\u003c/span\u003e), the number of nodes in the tree\n representing Pete’s mine. The remaining input consists of\n \u003cspan class\u003d\"tex2jax_process\"\u003e$n-1$\u003c/span\u003e lines, the\n \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003eth of which (starting\n at \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e) contains three\n integers \u003cspan class\u003d\"tex2jax_process\"\u003e$p_ i$\u003c/span\u003e,\n \u003cspan class\u003d\"tex2jax_process\"\u003e$x_ i$\u003c/span\u003e, and \u003cspan class\u003d\"tex2jax_process\"\u003e$y_ i$\u003c/span\u003e encoding information about the\n \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003eth node of the tree.\n \u003cspan class\u003d\"tex2jax_process\"\u003e$p_ i$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$0 \\leq p_ i \u0026lt; i$\u003c/span\u003e) is the index of\n the \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003eth node’s parent in\n the tree. A parent index of zero means that the node’s parent\n is the mine entrance (root of the tree). \u003cspan class\u003d\"tex2jax_process\"\u003e$x_ i$\u003c/span\u003e is the value of the ore in node\n \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e, and \u003cspan class\u003d\"tex2jax_process\"\u003e$y_ i$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq y_ i \\leq 1\\, 000$\u003c/span\u003e) is the\n length of the tunnel connecting node \u003cspan class\u003d\"tex2jax_process\"\u003e$p_ i$\u003c/span\u003e to node \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e. Exactly one node has \u003cspan class\u003d\"tex2jax_process\"\u003e$x_ i\u003d -1$\u003c/span\u003e, indicating that the node\n contains the motherlode; all other inputs satisfy \u003cspan class\u003d\"tex2jax_process\"\u003e$0 \\leq x_ i \\leq 1\\, 000.$\u003c/span\u003e\u003c/p\u003e\n \u003cp\u003eNote that node zero is the mine entrance; it contains no ore\n and has no corresponding line in the input. You may assume that\n the motherlode is a leaf of the tree (no node has the\n motherlode node as a parent).\u003c/p\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003ePrint two space-separated integers \u003cspan class\u003d\"tex2jax_process\"\u003e$a$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$b$\u003c/span\u003e, the worst-case and best-case\n investment Pete needs in order to clear a path to the\n motherlode, as described in more detail above.\u003c/p\u003e\n \u003ch2\u003eSample Explanation\u003c/h2\u003e\n \u003cp\u003eConsider the mine described in sample input \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e and illustrated in Figure\u0026nbsp;1.\n Pete needs \u003cspan class\u003d\"tex2jax_process\"\u003e$8$\u003c/span\u003e dollars to\n guarantee he reaches the motherlode even with poor digging\n choices: in the worst-case scenario he spends \u003cspan class\u003d\"tex2jax_process\"\u003e$2$\u003c/span\u003e dollars to completely clear the\n tunnel leading into pocket \u003cspan class\u003d\"tex2jax_process\"\u003e$2$\u003c/span\u003e, and then \u003cspan class\u003d\"tex2jax_process\"\u003e$5$\u003c/span\u003e more dollars to clear the tunnel\n leading to pocket \u003cspan class\u003d\"tex2jax_process\"\u003e$4$\u003c/span\u003e.\n With his last dollar he either digs his way to the motherlode,\n or opens the tunnel to pocket \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e, which gives him enough money to\n reach the motherlode in the next round of digging. In the\n best-case scenario he needs only one dollar: he spends that\n dollar to first dig through the tunnel leading into pocket\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e, and with the\n \u003cspan class\u003d\"tex2jax_process\"\u003e$3$\u003c/span\u003e dollars of ore he\n mines there, he can dig through the two tunnels on the path\n from the entrance to the motherlode.\u003c/p\u003e\n \u003cp\u003eA second example is provided in sample input \u003cspan class\u003d\"tex2jax_process\"\u003e$2$\u003c/span\u003e which is also illustrated in\n Figure\u0026nbsp;1. In one worst-case scenario, Pete excavates three\n feet of the tunnel leading to pocket \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e, two feet of the tunnel leading to\n pocket \u003cspan class\u003d\"tex2jax_process\"\u003e$3$\u003c/span\u003e, and one foot\n of the tunnel leading to pocket \u003cspan class\u003d\"tex2jax_process\"\u003e$4$\u003c/span\u003e, all without mining any ore. This\n costs him \u003cspan class\u003d\"tex2jax_process\"\u003e$6$\u003c/span\u003e dollars.\n With a seventh dollar, Pete is guaranteed to tunnel into an ore\n pocket which finances exploration of the rest of the mine\n (including the motherlode). In the best-case scenario, Pete\n needs only a single dollar: he first digs to pocket\n \u003cspan class\u003d\"tex2jax_process\"\u003e$2$\u003c/span\u003e, then \u003cspan class\u003d\"tex2jax_process\"\u003e$4$\u003c/span\u003e, then \u003cspan class\u003d\"tex2jax_process\"\u003e$3$\u003c/span\u003e, then \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e, finding the motherlode.\u003c/p\u003e\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\n0 3 1\n0 0 2\n2 -1 1\n2 0 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e8 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n \u003ch2\u003eSample 2\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\n0 -1 4\n0 2 1\n0 4 3\n0 3 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e7 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}