E - MST + 1 Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

N 頂点 M 辺の重み付き無向連結グラフ G が与えられます。G には自己ループや多重辺が含まれている可能性があります。
頂点には頂点 1, 頂点 2, \dots, 頂点 N と番号がついています。
辺には辺 1, 辺 2, \dots, 辺 M と番号がついています。辺 i は頂点 a_i と頂点 b_i を結ぶ重み c_i の辺です。ここで、1 \leq i \lt j \leq M を満たすすべての整数の組 (i, j) について c_i \neq c_j が成り立ちます。

以下で説明される Q 個のクエリに答えてください。
i 番目のクエリでは整数の組 (u_i, v_i, w_i) が与えられます。ここで、1 \leq j \leq M を満たすすべての整数 j について w_i \neq c_j が成り立ちます。
頂点 u_i と頂点 v_i を結ぶ重み w_i の無向辺を e_i として、G に e_i を追加してできるグラフ G_i を考えます。 このとき G_i の最小全域木 T_i は一意に定まることが証明できますが、T_i に e_i は含まれるでしょうか？答えを Yes あるいは No で出力してください。

ここで、クエリの前後で G は変化しないことに注意してください。言い換えると、クエリ i で G に e_i を追加したグラフを考えたとしても、他のクエリで出てくる G に e_i が追加されていることはありません。

最小全域木とは？ G の 全域木 とは、G に含まれるすべての頂点と G に含まれる辺の一部からなる木のことを言います。
G の 最小全域木 とは、G の全域木の中で辺の重みの和が最小である木のことを言います。

制約

  • 2 \leq N \leq 2 \times 10^5
  • N - 1 \leq M \leq 2 \times 10^5
  • 1 \leq a_i \leq N (1 \leq i \leq M)
  • 1 \leq b_i \leq N (1 \leq i \leq M)
  • 1 \leq c_i \leq 10^9 (1 \leq i \leq M)
  • c_i \neq c_j (1 \leq i \lt j \leq M)
  • グラフ G は連結である。
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq u_i \leq N (1 \leq i \leq Q)
  • 1 \leq v_i \leq N (1 \leq i \leq Q)
  • 1 \leq w_i \leq 10^9 (1 \leq i \leq Q)
  • w_i \neq c_j (1 \leq i \leq Q, 1 \leq j \leq M)
  • 入力はすべて整数である。

入力

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

N M Q
a_1 b_1 c_1
a_2 b_2 c_2
\vdots
a_M b_M c_M
u_1 v_1 w_1
u_2 v_2 w_2
\vdots
u_Q v_Q w_Q

出力

Q 行出力せよ。i 行目ではクエリ i への答えを Yes または No で出力せよ。

入力例 1

5 6 3
1 2 2
2 3 3
1 3 6
2 4 5
4 5 9
3 5 8
1 3 1
3 4 7
3 5 7

出力例 1

Yes
No
Yes

以下では頂点 u と頂点 v を結ぶ重み w の無向辺を (u,v,w) と表します。 G を図に表したものを以下に挙げます。

image

たとえばクエリ 1 では G に e_1 = (1,3,1) を追加したグラフ G_1 を考えます。G_1 の最小全域木 T_1 の辺集合は \lbrace (1,2,2),(1,3,1),(2,4,5),(3,5,8) \rbrace であり e_1 を含みます。よって Yes を出力します。

入力例 2

2 3 2
1 2 100
1 2 1000000000
1 1 1
1 2 2
1 1 5

出力例 2

Yes
No

Score : 500 points

Problem Statement

Given is a weighted undirected connected graph G with N vertices and M edges, which may contain self-loops and multi-edges.
The vertices are labeled as Vertex 1, Vertex 2, \dots, Vertex N.
The edges are labeled as Edge 1, Edge 2, \ldots, Edge M. Edge i connects Vertex a_i and Vertex b_i and has a weight of c_i. Here, for every pair of integers (i, j) such that 1 \leq i \lt j \leq M, c_i \neq c_j holds.

Process the Q queries explained below.
The i-th query gives a triple of integers (u_i, v_i, w_i). Here, for every integer j such that 1 \leq j \leq M, w_i \neq c_j holds.
Let e_i be an undirected edge that connects Vertex u_i and Vertex v_i and has a weight of w_i. Consider the graph G_i obtained by adding e_i to G. It can be proved that the minimum spanning tree T_i of G_i is uniquely determined. Does T_i contain e_i? Print the answer as Yes or No.

Note that the queries do not change T. In other words, even though Query i considers the graph obtained by adding e_i to G, the G in other queries does not have e_i.

What is minimum spanning tree? The spanning tree of G is a tree with all of the vertices in G and some of the edges in G.
The minimum spanning tree of G is the tree with the minimum total weight of edges among the spanning trees of G.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • N - 1 \leq M \leq 2 \times 10^5
  • 1 \leq a_i \leq N (1 \leq i \leq M)
  • 1 \leq b_i \leq N (1 \leq i \leq M)
  • 1 \leq c_i \leq 10^9 (1 \leq i \leq M)
  • c_i \neq c_j (1 \leq i \lt j \leq M)
  • The graph G is connected.
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq u_i \leq N (1 \leq i \leq Q)
  • 1 \leq v_i \leq N (1 \leq i \leq Q)
  • 1 \leq w_i \leq 10^9 (1 \leq i \leq Q)
  • w_i \neq c_j (1 \leq i \leq Q, 1 \leq j \leq M)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M Q
a_1 b_1 c_1
a_2 b_2 c_2
\vdots
a_M b_M c_M
u_1 v_1 w_1
u_2 v_2 w_2
\vdots
u_Q v_Q w_Q

Output

Print Q lines. The i-th line should contain the answer to Query i: Yes or No.

Sample Input 1

5 6 3
1 2 2
2 3 3
1 3 6
2 4 5
4 5 9
3 5 8
1 3 1
3 4 7
3 5 7

Sample Output 1

Yes
No
Yes

Below, let (u,v,w) denote an undirected edge that connects Vertex u and Vertex v and has the weight of w. Here is an illustration of G:

image

For example, Query 1 considers the graph G_1 obtained by adding e_1 = (1,3,1) to G. The minimum spanning tree T_1 of G_1 has the edge set \lbrace (1,2,2),(1,3,1),(2,4,5),(3,5,8) \rbrace, which contains e_1, so Yes should be printed.

Sample Input 2

2 3 2
1 2 100
1 2 1000000000
1 1 1
1 2 2
1 1 5

Sample Output 2

Yes
No