题目描述

求一棵 $N-2$ 条边权确定的树中那条不确定的边的边权分别为 $[L,R]$ 中的每一个数时，树中路径权值 $\text{gcd}$ 为 $1$ 的点对有多少。

路径的 $\text{gcd}$ 为路径上所有边权的 $\text{gcd}$。

输入格式

第一行 $N, L, R$。

第二行是不确定的边的两个端点。

接下来 $N-2$ 行每行三个数表示一条边的两个端点和边权。

输出格式

$R-L+1$ 行，第 $i$ 行为当不确定边权等于 $L+i-1$ 时的答案。

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

6
3
2
3
5

数据规模与约定

对于 $30$ 的数据，满足 $N \leq 1000, R - L \leq 1000$；

对于另外的 $30$ 的数据，满足 $N \leq 10^5, L = R$；

对于 $100$ 的数据，满足 $N \leq 10^5, D_i \leq 10^5, 1 \leq L \leq R \leq 10^5$。

传题人: 「注意：版权归杨乐所属！！」