当前没有测试数据。

路径覆盖

题目描述

有$n$个城市，城市之间有一些道路，城市和道路刚好组成了一棵树。给定$m$条树上路径（$A$,$B$），有$Q$个询问，每组询问给定两个正整数$L$,$R$（$1 \leq L \leq R \leq m$），求被从第$L$条路径到第$R$条路径覆盖了$R-L+1$次的边的总长度。

输入格式

第一行为一个正整数$n$。

接下来$n-1$行，每行包含三个正整数$x$,$y$,$z$，表示边（$x$,$y$）和边的长度$z$。

接下来一行一个正整数$m$，表示$m$条树上路径。

接下来$m$行，每行包含两个正整数$A$,$B$，表示第$i$条树上路径（$A$,$B$）。

接下来一行一个正整数$Q$。

接下来$Q$行，每行两个整数$L$,$R$，表示询问被从第$L$条路径到第$R$条路径覆盖了$R-L+1$次的边的总长度。

输出格式

输出$Q$行，第$i$个询问的答案。

数据范围与提示

• 对于$10\%$的数据，满足$n$，$m$，$Q \leq 200$；
• 对于$40\%$的数据，满足$n$，$m$，$Q \leq 1000$；
• 对于$80\%$的数据，满足$n$，$m$，$Q \leq 5 \times 10^{4}$；
• 对于$100\%$的数据，满足$1 \leq n$，$m \leq 2 \times 10^{5}$，$1 \leq Q \leq 1.4 \times 10^{6}$，$0 \leq z \leq 10^{9}$，$1 \leq L \leq R \leq m$，$1 \leq x$，$y$，$A$，$B \leq n$。

样例

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

5