最小生成树 + 1

题目描述

给定一个带权无向连通图 $G$，它有 $N$ 个顶点和 $M$ 条边，可能包含自环和重边。

顶点编号为顶点 $1$、顶点 $2$、$\dots$、顶点 $N$。

边编号为边 $1$、边 $2$、$\ldots$、边 $M$。边 $i$ 连接顶点 $a_i$ 和顶点 $b_i$，权重为 $c_i$。这里，对于任意满足 $1 \le i \lt j \le M$ 的整数对 $(i, j)$，都有 $c_i \neq c_j$。

请处理以下 $Q$ 个查询。

第 $i$ 个查询给出一个三元组 $(u_i, v_i, w_i)$。这里，对于任意满足 $1 \le j \le M$ 的整数 $j$，都有 $w_i \neq c_j$。

设 $e_i$ 是连接顶点 $u_i$ 和顶点 $v_i$、权重为 $w_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$ 的所有生成树中边权总和最小的树。

输入格式

输入按以下格式从标准输入给出：

$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。

样例

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

Yes
No
Yes

下面用 $(u,v,w)$ 表示连接顶点 $u$ 和顶点 $v$、权重为 $w$ 的无向边。

例如，查询 $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 3 2
1 2 100
1 2 1000000000
1 1 1
1 2 2
1 1 5

Yes
No

数据范围

• $2 \le N \le 2 \times 10^5$
• $N - 1 \le M \le 2 \times 10^5$
• $1 \le a_i \le N$ $(1 \le i \le M)$
• $1 \le b_i \le N$ $(1 \le i \le M)$
• $1 \le c_i \le 10^9$ $(1 \le i \le M)$
• $c_i \neq c_j$ $(1 \le i \lt j \le M)$
• 图 $G$ 是连通的。
• $1 \le Q \le 2 \times 10^5$
• $1 \le u_i \le N$ $(1 \le i \le Q)$
• $1 \le v_i \le N$ $(1 \le i \le Q)$
• $1 \le w_i \le 10^9$ $(1 \le i \le Q)$
• $w_i \neq c_j$ $(1 \le i \le Q, 1 \le j \le M)$
• 输入中的所有值均为整数。