P4565 [CTSC2018] Bugged Brute Force

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.

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 a single integer on one line: the output of temporaryDO’s program.

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|No $2$|$366$|$=1$|No|No $3$|$1388$|$>0$|No|No $4$|$1999$|$>0$|No|No $5$|$2666$|$>0$|No|No $6$|$5666$|none|No|No $7$|$8666$|none|No|No $8$|$11111$|none|No|No $9$|$12345$|none|No|No $10$|$366666$|$>0$|Yes|Yes $11$|$366666$|none|Yes|Yes $12\sim 13$|$366666$|$>0$|Yes|No $14$|$366666$|none|Yes|No $15\sim 16$|$366666$|$>0$|No|Yes $17$|$366666$|none|No|Yes $18\sim 20$|$366666$|none|No|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