Problem Description

Given a tree with $n$ nodes, find $3$ edges such that the endpoints of these three edges can reach each other by traversing only these three edges, and the sum of the lengths of the three edges is as large as possible.

Input Format

The first line contains an integer $n$, representing the number of nodes in the tree.

The next $n - 1$ lines each contain two integers separated by a single space. In the $i$-th line, the two numbers $x_i, y_i$ mean that there is an edge of length $y_i$ between node $i + 1$ and node $x_i$.

Output Format

Output one line containing one integer, representing the maximum possible sum of the lengths of the three edges that satisfy the requirement.

5
1 1
2 1
3 7
1 10

12

Hint

[Sample Explanation 1]

The edge length between node $2$ and node $1$ is $1$, the edge length between node $3$ and node $2$ is $1$, the edge length between node $4$ and node $3$ is $7$, and the edge length between node $5$ and node $1$ is $10$.

[Test Case Scale and Assumptions]

For $20\%$ of the test cases, $4 \le n \le 300$.
For $40\%$ of the test cases, $4 \le n \le 5000$.
For all test cases, $4 \le n \le 2 \times 10^5$, $1 \le x_i < i$, and $1 \le y_i \le 10^9$.

Translated by ChatGPT 5