Ex - Difference of Distance Editorial /

Time Limit: 5 sec / Memory Limit: 1024 MB

配点 : 625 点

問題文

頂点には 1 から N の番号が、辺には 1 から M の番号がついた N 頂点 M 辺の連結無向グラフがあります。 辺 i は頂点 U_i と頂点 V_i を結んでおり、重みとして整数 W_i が定められています。 ここで、1\leq s,t \leq N,\ s\neq t に対して d(s,t) を以下で定義します。

  • 頂点 s と頂点 t を結ぶすべてのパスに対する「パス上の辺の重みの最大値」の最小値

今から与えられる Q 個のクエリにそれぞれ答えてください。j 番目のクエリは以下の通りです。

  • A_j,S_j,T_j が与えられる。辺 A_j の重みを 1 増やすと d(S_j,T_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
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

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

上の図においては、辺の番号を黒字で、辺の重みを青字で表記しています。

1 番目から 6 番目のクエリについて説明します。

まず与えられたグラフにおける d(4,6) について考えます。 4 \rightarrow 1 \rightarrow 2 \rightarrow 6 というパス上の辺の重みの最大値は 5 ですが、 これは頂点 4 と頂点 6 を結ぶパスの中での最小値であるため、d(4,6)=5 です。

次に、辺 x\ (1 \leq x \leq 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 2
1 2 1
1 2 1
1
1 1 2

出力例 2

0

与えられるグラフは多重辺を含むこともあります。

Score : 625 points

Problem Statement

We have a connected undirected graph with N vertices numbered 1 to N and M edges numbered 1 to M. Edge i connects vertex U_i and vertex V_i, and has an integer weight of W_i. For 1\leq s,t \leq N,\ s\neq t, let us define d(s,t) as follows.

  • For every path connecting vertex s and vertex t, consider the maximum weight of an edge along that path. d(s,t) is the minimum value of this weight.

Answer Q queries. The j-th query is as follows.

  • You are given A_j,S_j,T_j. By what value will d(S_j,T_j) increase when the weight of edge A_j is increased by 1?

Note that each query does not actually change the weight of the edge.

Constraints

  • 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
  • The given graph is connected.
  • 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
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print Q lines. The j-th line (1\leq j \leq Q) should contain the answer to the j-th query.

Sample Input 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

Sample Output 1

0
0
0
0
0
1
1

image of the given graph

The above figure shows the edge numbers in black and the edge weights in blue.

Let us explain the first through sixth queries.

First, consider d(4,6) in the given graph. The maximum weight of an edge along the path 4 \rightarrow 1 \rightarrow 2 \rightarrow 6 is 5, which is the minimum over all paths connecting vertex 4 and vertex 6, so d(4,6)=5.

Next, consider the increment of d(4,6) when the weight of edge x\ (1 \leq x \leq 6) increases by 1. When x=6, we have d(4,6)=6, and the increment is 1. On the other hand, when x \neq 6, we have d(4,6)=5, and the increment is 0. For instance, when x=3, the maximum weight of an edge along the path 4 \rightarrow 1 \rightarrow 2 \rightarrow 6 is 6, but the maximum weight of an edge along the path 4 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 6 is 5, so d(4,6) is still 5.

Sample Input 2

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

Sample Output 2

0

The given graph may contain multi-edges.