3631. 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 n1 bi-directional paths connecting them, forming a tree. The length of the i-th path is wi, meaning that the time we have to spend walking through this path is wi.

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 si to city ti. 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 (1n2105).

The next n1 lines tell about the path information from path 1 to path n1, the i-th of which contains three space-separated integers ui, vi and wi (1ui,vin, uivi, 1wi1000).

The next line contains one integer q (1q2105).

The next q lines each contains two space-separated integers si and ti (1si,tin,siti).

输出格式

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.

54 人解决,69 人已尝试。

72 份提交通过,共有 357 份提交。

4.2 EMB 奖励。

创建: 6 年,6 月前.

修改: 6 年,6 月前.

最后提交: 1 年,7 月前.

来源: EOJ Monthly 2018.8

题目标签