D. Delivery Service

**单点时限: **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.

Input

5 1 2 2 1 3 3 3 4 3 3 5 4 2 1 5 4 2

Output

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$.

通知

比赛状态发生变化，点 OK 刷新。

通知