单点时限: 2.5 sec
内存限制: 512 MB
EOJ Delivery Service Company handles a massive amount of orders in our nation. As is well known, our nation has $n$ cities, with $n-1$ bi-directional paths connecting them, forming a tree. The length of the $i$-th path is $w_i$, meaning that the time we have to spend walking through this path is $w_i$.
Now, you, as the headquarter of EOJ, has somehow learned a magic spell. Each time you cast a spell on two paths, the lengths of these two paths magically swap with each other. You can do this magic as many times as you want (possibly none).
We have $q$ orders waiting to be handled. The $i$-th order demands sending a package from city $s_i$ to city $t_i$. We kindly ask you to do your magic before all the deliveries start, such that the total time we have to spend on delivering these packages is minimized.
The first line of the input contains one single integer $n$ ($1 \le n \le 2 \cdot 10^5$).
The next $n-1$ lines tell about the path information from path $1$ to path $n-1$, the $i$-th of which contains three space-separated integers $u_i$, $v_i$ and $w_i$ ($1 \le u_i, v_i \le n$, $u_i \neq v_i$, $1 \le w_i \le 1000$).
The next line contains one integer $q$ ($1 \le q \le 2 \cdot 10^5$).
The next $q$ lines each contains two space-separated integers $s_i$ and $t_i$ ($1 \le s_i, t_i \le n, s_i \neq t_i$).
Output one integer, the minimum total time you can achieve.
5 1 2 2 1 3 3 3 4 3 3 5 4 2 1 5 4 2
14
In the example, we swap the weights between edge $(1,2)$ and $(1,3)$, so that the first order takes $2+4=6$ time units to complete; the second order takes $2+3+3=8$ time units. Thus the total time is $14$.