3770. 约束平衡点集

【题目描述】

给定一张 $n$ 个点 $m$ 条边的带权无向图 $G$，其顶点从 $1∼n$ 编号，且边权为互不相等的正整数。

·对于任意两个不同的点 $u,v$ ，定义 $u$ 对 $v$ 的正约束值 $S_{u,v}$ 为最小的正整数 $c$ ，使得存在一条从 $u$ 到 $v$ 的路径，路径上的边权全部不大于 $c$ 。

·对于任意两个不同的点 $u,v$ ，定义 $u$ 对 $v$ 的负约束值 $T_{u,v}$ 为最大的正整数 $c$ ，使得存在一条从 $u$ 到 $v$ 的路径，路径上的边权全部不小于 $c$ 。

·对于任意一个二元点对 $ε=\{u,v\}$ $(u≠v)$ ，定义 $ε$ 的约束平衡点集 $E_ε$ 包含所有异于 $u,v$ 的点 $p$，使得 $S_{u,p}=S_{p,v},T_{u,p}=T_{p,v}$。

现在有 $q$ 组询问，每次给定一个二元点对 $ε$，求 $card(E_ε)$。

【输入格式】

第一行两个整数 $n,m$，分别表示图中的顶点数、边数。

接下来 $m$ 行每行三个整数 $x_i,y_i,w_i$ ，表示一条 $x_i,y_i$ 间存在一条边权为 $w_i$ 的边。

本题询问强制在线，具体细节见下。

接下来一行两个整数 $q,k$。其中 $k∈\{0,1\}$

接下来 $q$ 行每行两个整数 $u_0,v_0$ ，我们令上次询问的答案为 $x$（如果这是第一次询问，则 $x=0$ ），则令 $u=(u_0+k*x)\%n+1\ ,\ v=(v_0+k*x)\%n+1$ ，表示一个二元点对 $ε=\{u,v\}$，你需要回答 $card(E_ε)$。

特殊的，若计算出的 $u=v$ ，则令 $u=(u+1)\%n+1$。

数据保证给出的图 $G$ 连通，并且图中不包含重边与自环。

【输出格式】

对于每个询问输出一行一个整数表示答案。

【样例输入1】

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

【样例输出1】

1
0

【样例说明1】

对于第一个询问，$u=2,v=3$，$E_ε=\{4\}$。

因为 $S_{2,4}=S_{4,3}=3\ ,\ T_{2,4}=T_{4,3}=4$。

对于第二个询问，$u=2,v=4$，$E_ε= ∅ $。

【样例输入2】

8 12
1 2 10
1 3 3
2 4 11
2 5 12
3 4 1
3 5 2
4 6 13
5 6 14
4 7 4
5 7 5
6 8 15
7 8 6
2 0
3 4
4 7

【样例输出2】

3
1

【样例说明2】

本样例不强制在线。

对于第一个询问，$u=4,v=5$，$E_ε=\{1,2,7\}$。

因为 $S_{4,1}=S_{1,5}=3\ ,\ T_{4,1}=T_{1,5}=10$。

$S_{4,2}=S_{2,5}=3\ ,\ T_{4,2}=T_{2,5}=10$。

$S_{4,7}=S_{7,5}=4\ ,\ T_{4,7}=T_{7,5}=6$。

【数据规模与约定】

对于所有测试数据，保证 $1≤n,q≤2 \times 10^5\ ,\ n-1≤m≤4×10^5\ .\ 1 \le w_i \lt 2^{31}\ ,\ k∈\{0,1\}$。

每个测试点的具体限制见下表：

特殊性质A：图的形态是一条链。

特殊性质B：$k=0$。

【来源】

$rsr$