Description

temporaryDO is a very weak OIer. In April, during the provincial team qualifier, he saw the problem “Link-Cut Tree.” The partial score for $k = 0$ asks for the longest path on tree $T$. Poor temporaryDO didn’t know how to solve it; even after scratching his head, he couldn’t come up with any idea.

At that moment, the kind Banban appeared in the air, radiating a brilliant yet gentle light that rippled across the exam hall. “The problem isn’t hard,” Banban said. That magnetic voice filled temporaryDO with strength.

He decided to write an $O(n^2 \log n)$ partial-solution program for $k = 0$ that enumerates pairs and uses LCA to compute distances. So temporaryDO chose $1$ as the root, built a heavy-light decomposition structure for LCA, and then wrote a double for loop to enumerate pairs.

However, clumsy temporaryDO accidentally allocated an array too small, causing an out-of-bounds access into a mysterious memory region. Coincidentally, that region happened to store another tree $T'$. As a result, the program did not RE, but when computing the distance between $x$ and $y$, it calculated

$$\mathrm{depth}(x) + \mathrm{depth}(y) - ({\mathrm{depth}(\mathrm{LCA}(x,y))}+{\mathrm{depth'}(\mathrm{LCA'}(x,y))})$$

Finally, the program outputs the maximum of the above-defined “distance” over all pairs $i, j$ with $i \le j$. temporaryDO’s program gloriously scored zero during evaluation. Unconvinced, he decided to spend several days reproducing his program’s output. Given $T$ and $T'$, please help the poor temporaryDO compute what his program outputs.

Input Format

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

Lines $2$ to $n$ each contain three integers $x, y, v$, indicating that in $T$ there is an edge between $x$ and $y$ with length $v$.

Lines $n + 1$ to $2n - 1$ each contain three integers $x, y, v$, indicating that in $T'$ there is an edge between $x$ and $y$ with length $v$.

Output Format

Output a single integer on one line: the output of temporaryDO’s program.

6
1 2 2
1 3 0
2 4 1
2 5 -7
3 6 0
1 2 -1
2 3 -1
2 5 3
2 6 -2
3 4 8

5

Hint

Sample explanation 1
For the pair $(3, 4)$, the distance is computed as $3 + 0 - (0 + (-2)) = 5$.

Constraints
For all testdata, $1 \le n \le 366666$, $|v| \le 2017011328$. Detailed constraints are shown in the table below; in the table, “无” means no special restriction.

测试点编号	$n \le$	$v$	$T$ is a path	$T'$ is a path
$1$	$36$	$=1$	No
$2$	$366$
$3$	$1388$	$>0$
$4$	$1999$
$5$	$2666$
$6$	$5666$	none
$7$	$8666$
$8$	$11111$
$9$	$12345$
$10$	$366666$	$>0$	Yes	Yes
$11$		none
$12\sim 13$		$>0$		No
$14$		none
$15\sim 16$		$>0$	No	Yes
$17$		none
$18\sim 20$				No

$\mathrm{depth}(p)$ and $\mathrm{depth'}(p)$ denote the distances from node $1$ to node $p$ in trees $T$ and $T'$ respectively. Here, distance means the sum of edge weights along the path, and $\mathrm{depth}(1) = 0$.

$\mathrm{LCA}(x, y)$ and $\mathrm{LCA'}(x, y)$ denote, in $T$ and $T'$ respectively, the lowest common ancestor of nodes $x$ and $y$, i.e., the point on the shortest path from $x$ to $y$ that has the fewest edges from the root.

Translated by ChatGPT 5