Problem Description
给定一棵n个点的树,以及m条路径,每次询问第L条到第R条路径的交集部分的长度(如果一条边同时出现在2条路径上,那么它属于路径的交集)。
Input
第一行一个数n(n<=500,000)
接下来n-1行,每行三个数x,y,z,表示一条从x到y并且长度为z的边
第n+1行一个数m(m<=500,000)
接下来m行,每行两个数u,v,表示一条从u到v的路径
接下来一行一个数Q,表示询问次数(Q<=500,000)
接下来Q行,每行两个数L和R
Output
Q行,每行一个数表示答案。
Sample Input
4
1 2 5
2 3 2
1 4 3
2
1 2
3 4
1
1 2
Sample Output
5