MST + 1

题目描述

给定一个带权无向连通图 $G$，它有 $N$ 个顶点和 $M$ 条边，图中可能包含自环和多重边。
顶点按 Vertex $1$, Vertex $2$, $\dots$, Vertex $N$ 标号。
边按 Edge $1$, Edge $2$, $\ldots$, Edge $M$ 标号。边 $i$ 连接顶点 $a_i$ 和顶点 $b_i$，权重为 $c_i$。这里，对于任意整数对 $(i, j)$ 满足 $1 \leq i \lt j \leq M$，都有 $c_i \neq c_j$。
处理下面给出的 $Q$ 个查询。
第 $i$ 个查询给出一个整数三元组 $(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$ 的无向边。考虑通过将 $e_i$ 加入 $G$ 得到的图 $G_i$。可以证明 $G_i$ 的最小生成树 $T_i$ 是唯一确定的。问 $T_i$ 是否包含 $e_i$？输出答案 $Yes$ 或 $No$。 注意查询并不改变 $T$。换句话说，尽管查询 $i$ 考虑了将 $e_i$ 加入 $G$ 得到的图，但在其他查询中所考虑的 $G$ 中并不包含 $e_i$。

输入格式

输入从标准输入按以下格式给出： $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

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

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 \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)$ 输入中的所有数值均为整数。下面记作 $(u,v,w)$ 表示一条连接顶点 $u$ 和顶点 $v$ 且权重为 $w$ 的无向边。 下面是图 $G$ 的示意图： 例如，查询 $1$ 考虑通过加入 $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$。

标签: AtCoder|abc235E

来源

AtCoder|abc235E