← 返回题目列表

AtCoder · abc301_h

Ex. 距离差异

中文机器翻译题面 查看原题

分数: 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

image of the given graph

上图以黑色显示边数,以蓝色显示边权重。

让我们解释一下第一个到第六个查询。

首先,考虑 给定图中的 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

给定的图可能包含多边。