4212. [Ynoi2006]rldcot

【题目描述】

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

定义 $d_x$ 表示点 $x$ 到根简单路径上边权的和，$\text{LCA}(x,y)$ 表示 $x,y$ 节点在树上的最近公共祖先。

共 $m$ 组询问，每次询问给出 $l,r$，求对于所有点编号的二元组 $(i,j)$ 满足 $l \le i,j \le r$ ，有多少种不同的 $d_{\text{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

【数据规模与约定】

对于 $10\%$ 的数据，满足 $1\le n,m \le 100$。

对于另外 $20\%$ 的数据，满足 $1\le n,m \le 5000$。

对于另外 $20\%$ 的数据，满足 $1\le n,m \le 50000$。

对于另外 $20\%$ 的数据，满足 $d=1$。

对于 $100\%$ 的数据，满足 $1\le n \le 10^5$，$1\le m \le 5 \times 10^5$，所有数值为整数，$-10^9 \le d \le 10^9$。

本题的第 $11$ 个测试点为 hack 数据；本题数据较水，如有错解通过请联系管理添加数据。

【来源】

Ynoi 2006。