给定一棵 n 个节点的树,树根为 1,每个点有一个编号,每条边有一个边权。
定义 dep(x) 表示一个点到根简单路径上边权的和,lca(x,y) 表示 x,y 节点在树上的最近公共祖先。
共 m 组询问,每次询问给出 l,r,求对于所有点编号的二元组 (i,j) 满足 l≤i,j≤r ,有多少种不同的 dep(lca(i,j))。
输入格式
第一行两个用空格隔开的数 n,m。
之后 n−1 行,每行三个用空格隔开的数 u,v,d 表示一条 u 到 v 边权为 d 的边。
之后 m 行,每行两个用空格隔开的数 l,r 表示一次询问。
输出格式
共 m 行,一行一个整数,表示询问的答案。
样例数据
样例 1 输入
10 19
9 1 -4
9 8 2
8 10 5
9 7 -3
1 4 2
10 2 5
10 5 -1
7 3 -3
10 6 5
8 10
4 6
1 7
7 9
5 5
7 8
8 10
10 10
10 10
9 10
5 7
8 8
6 6
2 8
9 10
4 8
5 5
1 6
1 2
样例 1 输出
3
4
7
3
1
3
3
1
1
2
5
1
1
8
2
7
1
6
2
样例 2 输入
10 19
6 1 299830931
1 4 -565297395
1 7 -606073228
4 8 94253706
8 9 -576603423
4 3 116780102
3 5 620388954
7 10 -950023905
5 2 813045783
3 5
7 7
8 10
4 7
10 10
9 9
4 7
8 10
6 7
4 8
9 10
2 9
8 10
2 8
4 4
10 10
4 9
1 5
8 9
样例 2 输出
3
1
4
5
1
1
5
4
3
6
3
9
4
8
1
1
7
5
2
子任务
Idea:nzhtl1477,Solution:nzhtl1477,Code:lk,Data:nzhtl1477
对于 10% 的数据,满足 1≤n,m≤100。
对于另外 20% 的数据,满足 1≤n,m≤5000。
对于另外 20% 的数据,满足 1≤n,m≤50000。
对于另外 20% 的数据,满足 d=1。
对于 100% 的数据,满足 1≤n≤105,1≤m≤5×105,所有数值为整数,−109≤d≤109。