树上询问
暂无测试数据。
你有一棵 $n$ 个节点的树。树的边有边权。
定义树上两个节点 $i,j$ 的距离 $\text{dist}(i,j)$ 为 $i$ 到 $j$ 之间简单路径上的边权之和。
给出 $q$ 组询问，每次给定 $l,r,x$，你需要输出 $\sum_{i=l}^{r}\text{dist}(i,x)$ 的值。
这个值可能会很大，所以你需要将它对 $10^9+7$ 取模后再输出。
输入格式
第一行一个正整数 $n$ 表示节点个数。
接下来 $n-1$ 行，每行两个正整数 $u_i,v_i,w_i$ 表示树上存在一条边 $(u_i,v_i)$，其边权为 $w_i$。
接下来一个正整数 $q$ 表示询问次数。
接下来 $q$ 行，每行三个正整数 $l,r,x$，表示一次询问。
输出格式
对于每次询问，输出一行一个正整数表示答案。
数据范围
| 数据点编号 | 数据范围 |
|---|---|
| $1\sim 2$ | $n,q\le 10$ |
| $3\sim 4$ | $n,q\le 200$ |
| $5\sim 6$ | $u_i=i,v_i=i+1$ |
| $7\sim 8$ | $u_i=1$ |
| $9\sim 12$ | $w_i=1$ |
| $13\sim 14$ | $q\le 3$ |
| $15\sim 20$ | 无特殊限制 |
对于 $100\%$ 的数据，$n,q\le 10^5,w_i\le 10^{9}$。
4
1 2 1
1 3 2
2 4 4
4
3 4 1
2 2 4
1 2 3
2 3 1
7
4
5
3
8
1 2 6
1 3 8
2 7 1
3 4 8
3 5 1
3 6 7
7 8 1
9
1 7 3
5 6 1
1 2 5
6 8 3
4 5 1
1 6 6
1 1 7
6 6 2
3 6 2
53
24
24
38
25
66
7
21
72