P6199 [EER1] Kappa Heavy Industries

There are two kinds of youkai living on Youkai Mountain: Crow Tengu and Kappa. In the past, each of them had their own dedicated transportation network, which allowed travel between different places on Youkai Mountain. However, the maintenance cost of two separate networks is simply too high. So now the youkai want to simplify the two networks into one. This heavy project has been entrusted to Kappa Heavy Industries.

There are $n$ locations on Youkai Mountain. The two transportation networks of the Crow Tengu and the Kappa are each made up of some undirected roads connecting these locations, and each road has its own length. If we view these roads as weighted edges, then the two networks can be represented as two trees with $n$ nodes, $T_1$ and $T_2$ (a connected undirected weighted graph with $n-1$ edges). Kappa Heavy Industries now wants to build some new undirected roads. The cost to build a new undirected road $(i,j)$ is $dist_{T_1}(i,j)+dist_{T_2}(i,j)$, that is, the sum of the distances from $i$ to $j$ in $T_1$ and $T_2$. Kappa Heavy Industries must ensure that any two nodes on Youkai Mountain can reach each other using only the newly built roads. However, since spending too much may trigger an incident, they want the total cost of this project to be as small as possible. Nitori is the chief designer of this project. Please help her compute the minimum possible total cost of building the new roads.

The first line contains a positive integer $n$, representing the number of nodes. The next $n-1$ lines describe $T_1$. The $i$-th line contains three integers $x_i, y_i, v_i(1 \leq x_i, y_i \leq n, 1 \leq v_i \leq 5000)$, indicating that there is an edge in $T_1$ of length $v_i$ connecting nodes $x_i$ and $y_i$. The next $n-1$ lines describe $T_2$. The $j$-th line contains three integers $x_j, y_j, v_j(1 \leq x_j, y_j \leq n, 1 \leq v_j \leq 5000)$, indicating that there is an edge in $T_2$ of length $v_j$ connecting nodes $x_j$ and $y_j$.

Output one integer in a single line, representing the minimum total cost.

For $100\%$ of the testdata, $2 \leq n \leq 10^5$. This problem has $5$ subtasks, with the following limits: Subtask $1$ ($15$ points): guarantee $2 \leq n \leq 1000$. Subtask $2$ ($15$ points): guarantee that $T_1$ and $T_2$ are both chains. Subtask $3$ ($5$ points): guarantee that $T_1$ and $T_2$ are exactly the same except for edge weights (that is, if the two trees are viewed as unweighted trees, then they are the same). Subtask $4$ ($5$ points): guarantee that $T_2$ is a chain. Subtask $5$ ($60$ points): no special constraints. Translated by ChatGPT 5