分数: 625 点
问题陈述
我们有一个连通的无向图 N 顶点编号 1 to N 和 M 边编号 1 to M。 边缘 i 连接顶点 U_i 和顶点 V_i,并且整数权重为 W_i。 对于 1\leq s,t \leq N,\ s\neq t,让我们定义 d(s,t) 如下。
- 对于连接顶点的每个路径 s 和顶点 t,考虑沿该路径的边的最大权重。 d(s,t) 是该权重的最小值。
答案 Q 查询。的 j第查询如下。
- 你被给予 A_j,S_j,T_j。将通过什么值 d(S_j,T_j) 边权重增加时 A_j 增加 1?
请注意,每个查询实际上并不改变边的权重。
约束
- 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
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
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\leq j \leq Q) 应包含以下问题的答案 j- 第一个查询。
示例输入 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

上图以黑色显示边数,以蓝色显示边权重。
让我们解释一下第一个到第六个查询。
首先,考虑 给定图中的 d(4,6) 。 沿路径的边的最大权重 4 \rightarrow 1 \rightarrow 2 \rightarrow 6 is 5,这是连接顶点的所有路径中的最小值 4 和顶点 6,所以 d(4,6)=5.
接下来,考虑增量 d(4,6) 边权重时 x\ (1 \leq x \leq 6) 增加 1。 当 x=6,我们有 d(4,6)=6,增量为 1。另一方面,当 x \neq 6,我们有 d(4,6)=5,增量为 0。 例如,当 x=3,沿路径的边的最大权重 4 \rightarrow 1 \rightarrow 2 \rightarrow 6 is 6,但是沿路径的边的最大权重 4 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 6 is 5,所以 d(4,6) 仍然 5.
示例输入 2
2 2 1 2 1 1 2 1 1 1 1 2
示例输出 2
0
给定的图可能包含多边。