QOJ.ac

QOJ

Time Limit: 0.5 s Memory Limit: 512 MB Total points: 100
[0]

# 7444. rldcot

Statistics

给定一棵 n 个节点的树,树根为 1,每个点有一个编号,每条边有一个边权。

定义 dep(x) 表示一个点到根简单路径上边权的和,lca(x,y) 表示 x,y 节点在树上的最近公共祖先。

m 组询问,每次询问给出 l,r,求对于所有点编号的二元组 (i,j) 满足 li,jr ,有多少种不同的 dep(lca(i,j))

输入格式

第一行两个用空格隔开的数 n,m

之后 n1 行,每行三个用空格隔开的数 u,v,d 表示一条 uv 边权为 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% 的数据,满足 1n,m100

对于另外 20% 的数据,满足 1n,m5000

对于另外 20% 的数据,满足 1n,m50000

对于另外 20% 的数据,满足 d=1

对于 100% 的数据,满足 1n1051m5×105,所有数值为整数,109d109