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

例如,查询 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