← 返回题目列表

AtCoder · abc235_e

H. 最小生成树加一

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

分数: 500 点

问题陈述

给定的是一个加权无向连通图 G 与 N 顶点和 M 边,可能包含自环和多边。
顶点被标记为 Vertex 1,顶点 2, \dots,顶点 N.
边缘标记为 Edge 1,边缘 2, \ldots,边缘 M。边缘 i 连接顶点 a_i 和顶点 b_i 的重量为 c_i。这里,对于每对整数 (i, j) 这样 1 \leq i \lt j \leq M, c_i \neq c_j 成立。

处理 Q 查询解释如下。
的 i-th 查询给出整数的三倍 (u_i, v_i, w_i)。这里,对于每个整数 j 这样 1 \leq j \leq M, w_i \neq c_j 成立。
让 e_i 是连接顶点的无向边 u_i 和顶点 v_i 的重量为 w_i。考虑图表 G_i 通过添加获得 e_i to G。 可以证明最小生成树 T_i of G_i 是唯一确定的。是否 T_i 包含 e_i?将答案打印为 Yes or No.

请注意,查询不会改变 T。换句话说,即使查询 i 考虑通过添加获得的图 e_i to G, G 在其他查询中没有 e_i.

什么是最小生成树? 的 生成树 of G 是一棵树,其所有顶点位于 G 和一些边缘 G.
的 最小生成树 of 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 or 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) 表示连接 Vertex 的无向边 u 和顶点 v 的重量为 w。 这是一个说明 G:

image

例如,查询 1 考虑图表 G_1 通过添加获得 e_1 = (1,3,1) to G。最小生成树 T_1 of G_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