Description

给定一棵 $n$ 个点的树，以及 $m$ 条路径，每次询问第 $L$ 条到第 $R$ 条路径的交集部分的长度（如果一条边同时出现在 $2$ 条路径上，那么它属于路径的交集）。

Input Format

第一行一个数 $n（n<=5e5）$。接下来 $n-1$ 行，每行三个数 $x，y，z$，($1 <= x, y <= n, 1 <= z <= 1e9$)表示一条从 $x$ 到 $y$ 并且长度为 $z$ 的边。第 $n+1$ 行一个数 $m$（$m<=5e5$）。接下来 $m$ 行，每行两个数 $u，v，(1 <= u, v <= n)$ 表示一条从 $u$ 到 $v$ 的路径。接下来一行一个数 $Q$，表示询问次数（$Q<=5e5$）。接下来 $Q$ 行，每行两个数 $L$ 和 $R(1 <= L <= R <= m)$。

Output Format

输出 $Q$ 行，对于每次询问，输出一行，该行包含一个正整数，表示询问的答案。

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

5

Source

Online Judge http://127.0.0.1