距离之差

题目描述

我们有一个连通无向图,包含编号为 $1$ 到 $N$ 的 $N$ 个顶点和编号为 $1$ 到 $M$ 的 $M$ 条边。 第 $i$ 条边连接顶点 $U_i$ 和顶点 $V_i$,权重为整数 $W_i$。 对 $1\le s,t \le N,\ s\neq t$,定义 $d(s,t)$ 如下。

对连接顶点 $s$ 和顶点 $t$ 的每一条路径,考虑该路径上的边的最大权重。$d(s,t)$ 是所有这些值的最小值。

回答 $Q$ 个查询。第 $j$ 个查询如下。

给你 $A_j,S_j,T_j$。当边 $A_j$ 的权重增加 $1$ 时,$d(S_j,T_j)$ 会增加多少?

注意,每个查询实际上并不会改变边的权重。

输入格式

输入按以下格式从标准输入给出:

$N$ $M$
$U_1$ $V_1$ $W_1$
$\vdots$
$U_M$ $V_M$ $W_M$
$Q$
$A_1$ $S_1$ $T_1$
$\vdots$
$A_Q$ $S_Q$ $T_Q$

输出格式

输出 $Q$ 行。 第 $j$ 行 $(1\le j \le Q)$ 应输出第 $j$ 个查询的答案。

样例

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

0
0
0
0
0
1
1

上图中黑色数字表示边的编号,蓝色数字表示边的权重。

下面说明第 1 到第 6 个查询。

首先,考虑原图中 $d(4,6)$。 路径 $4 \rightarrow 1 \rightarrow 2 \rightarrow 6$ 上的边的最大权重为 $5$,这是连接顶点 $4$ 和顶点 $6$ 的所有路径中的最小值,所以 $d(4,6)=5$。

接下来,考虑当边 $x\ (1 \le x \le 6)$ 的权重增加 $1$ 时,$d(4,6)$ 的增量。 当 $x=6$ 时,有 $d(4,6)=6$,增量为 $1$。另一方面,当 $x \neq 6$ 时,有 $d(4,6)=5$,增量为 $0$。 例如,当 $x=3$ 时,路径 $4 \rightarrow 1 \rightarrow 2 \rightarrow 6$ 上的边的最大权重为 $6$,但路径 $4 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 6$ 上的边的最大权重为 $5$,所以 $d(4,6)$ 仍为 $5$。

2 2
1 2 1
1 2 1
1
1 1 2

0

给定图可能包含重边。

数据范围

• $2\le N \le 2\times 10^5$
• $N-1\le M \le 2\times 10^5$
• $1 \le U_i,V_i \le N$
• $U_i \neq V_i$
• $1 \le W_i \le M$
• 给定图是连通的。
• $1\le Q \le 2\times 10^5$
• $1 \le A_j \le M$
• $1 \le S_j,T_j \le N$
• $S_j\neq T_j$
• 输入中的所有值均为整数。