Org Chart Mentorship Pairing Bonus

A fast-growing startup's org chart is a tree of n employees numbered 0 to n - 1, where employee 0 is the CEO and has no manager. For every other employee i (1 <= i <= n - 1), employee par_i is their direct manager, and the reporting relationship between employee i and par_i carries a mentorship bonus of score_i (a nonnegative integer measuring how well the pair works together).

HR wants to formalize a set of mentorship pairings, where each pairing links an employee directly to their own manager (a pairing may only use an existing reporting relationship, never any other pair of employees). To keep responsibilities clear, every employee -- whether acting as the manager or the report in a pairing -- may be part of at most one formalized pairing. Some employees may end up in zero pairings.

Determine the maximum possible sum of mentorship bonuses HR can lock in, subject to this one-pairing-per-employee limit.

Input format

• Line 1: a single integer n, the number of employees.
• Each of the next n - 1 lines describes one non-CEO employee, in increasing order of employee index (employee 1 first, then employee 2, ..., employee n - 1): two integers par_i and score_i, where par_i is the index of employee i's manager and score_i is the mentorship bonus of the reporting relationship between employee i and par_i.

Output format

Print a single integer: the maximum total mentorship bonus achievable.

Constraints

• 2 <= n <= 10^5
• For employee i (1 <= i <= n - 1): 0 <= par_i <= i - 1 (the reporting chain never points forward, guaranteeing a valid tree rooted at employee 0)
• 0 <= score_i <= 10^6

4
0 5
0 1
1 10

11

2
0 100

100