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。

输入输出样例 #1

输入 #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

输入输出样例 #2

输入 #2

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

输出 #2

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 翻译