AT_abc301_h [ABC301Ex] Difference of Distance

有一个 $N$ 个顶点 $M$ 条边的连通无向图，顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。第 $i$ 条边连接顶点 $U_i$ 和顶点 $V_i$，其权值为整数 $W_i$。对于 $1 \leq s, t \leq N, s \neq t$，定义 $d(s, t)$ 如下： - $d(s, t)$ 是所有连接顶点 $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$ 行输出第 $j$ 个查询的答案。

### 限制条件 - $2 \leq N \leq 2 \times 10^5$ - $N-1 \leq M \leq 2 \times 10^5$ - $1 \leq U_i, V_i \leq N$ - $U_i \neq V_i$ - $1 \leq W_i \leq M$ - 给定的图是连通的 - $1 \leq Q \leq 2 \times 10^5$ - $1 \leq A_j \leq M$ - $1 \leq S_j, T_j \leq N$ - $S_j \neq T_j$ - 所有输入均为整数 ### 样例解释 1  在上图中，边的编号用黑色表示，边的权值用蓝色表示。下面说明前 $1$ 到 $6$ 个查询。 首先，考虑给定图中 $d(4,6)$。路径 $4 \rightarrow 1 \rightarrow 2 \rightarrow 6$ 上的最大边权为 $5$，这是所有连接顶点 $4$ 和顶点 $6$ 的路径中最大边权的最小值，因此 $d(4,6)=5$。 接下来，考虑将第 $x$ 条边的权值增加 $1$ 后 $d(4,6)$ 的变化量（$1 \leq x \leq 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 给定的图可能包含重边。 由 ChatGPT 4.1 翻译