Shenko Chocolate Bar - Revolution#4807
Akim has won a gold medal at the IOI, and as a reward, he is eligible to receive a chocolate bar from the competition organizers. There are different types of chocolate bars made by the renowned Shenko chocolate factory, each with its own cost. Every type, except for the legendary "Kyiv Classic" chocolate bar, has a predecessor type. A predecessor can only be a chocolate bar that was introduced earlier. Historically, the first type is the iconic "Kyiv Classic".
Akim and an official are tasked with selecting a chocolate bar for Akim. Akim wants the most expensive chocolate bar, while the official aims to minimize the cost. The selection process begins with "Kyiv Classic". On his turn, Akim can either take the current chocolate bar or switch to a descendant chocolate bar, if available. The official, believing that newer types are inferior and cheaper, will switch to a descendant chocolate bar if possible, or otherwise, he will purchase the current chocolate bar for Akim. Akim makes the first move.
Your task is to determine the cost of the chocolate bar that Akim will ultimately receive.
The chocolate bar types are numbered in an arbitrary order, with "Kyiv Classic" being number . The first line of the input contains a single integer - the number of chocolate bar types (0 < N \leq 200000). The following lines each contain integers P_i and C_i - the predecessor type number of the -th type and the cost of the -th type (0 \leq P_i \leq N, 0 < C_i \leq 1000000000; for "Kyiv Classic", which has no predecessor, P_1 = 0 is specified).
Output a single integer - the cost of the chocolate bar that Akim will receive, assuming both he and the official make optimal choices.
Example 1