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$ 个查询的答案。

输入输出样例 #1

输入 #1

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

输出 #1

0
0
0
0
0
1
1

输入输出样例 #2

输入 #2

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

输出 #2

0

说明/提示

限制条件

• $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 翻译