AT_abc235_e [ABC235E] MST + 1

给定一个有 $N$ 个顶点、$M$ 条边的带权无向连通图 $G$。$G$ 可能包含自环和重边。 顶点编号为 $1$ 到 $N$。 边编号为 $1$ 到 $M$。第 $i$ 条边连接顶点 $a_i$ 和顶点 $b_i$，权值为 $c_i$。对于所有满足 $1 \leq i < j \leq M$ 的整数对 $(i, j)$，都有 $c_i \neq c_j$。 请回答下面描述的 $Q$ 个询问。 第 $i$ 个询问给出整数三元组 $(u_i, v_i, w_i)$。对于所有 $1 \leq j \leq M$，都有 $w_i \neq c_j$。 将连接顶点 $u_i$ 和顶点 $v_i$、权值为 $w_i$ 的无向边 $e_i$ 加入 $G$，得到新图 $G_i$。可以证明，$G_i$ 的最小生成树 $T_i$ 是唯一的。请判断 $T_i$ 是否包含 $e_i$。对于每个询问，输出 `Yes` 或 `No`。 注意，$G$ 在每次询问前后都不会发生变化。换句话说，对于第 $i$ 个询问，虽然考虑了在 $G$ 上加入 $e_i$ 得到 $G_i$，但其它询问中并不会出现 $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`。

### 数据范围 - $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 < 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)$ - 所有输入均为整数。 ### 样例解释 1 下面用 $(u, v, w)$ 表示连接顶点 $u$ 和顶点 $v$、权值为 $w$ 的无向边。$G$ 的结构如下图所示。  例如，对于第 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`。 由 ChatGPT 4.1 翻译