Score : $500$ points

问题描述

给定一个带权重的无向连通图 $G$，包含 $N$ 个顶点和 $M$ 条边，该图可能包含自环和平行边。 顶点被标记为顶点 $1$、顶点 $2$、$\dots$、顶点 $N$。 边被标记为边 $1$、边 $2$、$\ldots$、边 $M$。边 $i$ 连接顶点 $a_i$ 和顶点 $b_i$，其权重为 $c_i$。这里对于任意一对整数 $(i, j)$ 满足 $1 \leq i < 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$ 的无向边。考虑通过在 $G$ 中添加 $e_i$ 得到的图 $G_i$。可以证明 $G_i$ 的最小生成树 $T_i$ 是唯一确定的。问 $T_i$ 是否包含边 $e_i$？打印答案 Yes 或 No。

注意：查询不会改变原始的 $T$。换句话说，尽管第 $i$ 个查询考虑了通过在 $G$ 中添加 $e_i$ 得到的图，但在其他查询中的 $G$ 不包含 $e_i$。

什么是最小生成树？ 生成树 是 $G$ 中包含所有顶点及部分边构成的一棵树。 最小生成树 是 $G$ 的生成树中具有最小总边权重的那棵树。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

Given is a weighted undirected connected graph $G$ with $N$ vertices and $M$ edges, which may contain self-loops and multi-edges.
The vertices are labeled as Vertex $1$, Vertex $2$, $\dots$, Vertex $N$.
The edges are labeled as Edge $1$, Edge $2$, $\ldots$, Edge $M$. Edge $i$ connects Vertex $a_i$ and Vertex $b_i$ and has a weight of $c_i$. Here, for every pair of integers $(i, j)$ such that $1 \leq i \lt j \leq M$, $c_i \neq c_j$ holds.

Process the $Q$ queries explained below.
The $i$-th query gives a triple of integers $(u_i, v_i, w_i)$. Here, for every integer $j$ such that $1 \leq j \leq M$, $w_i \neq c_j$ holds.
Let $e_i$ be an undirected edge that connects Vertex $u_i$ and Vertex $v_i$ and has a weight of $w_i$. Consider the graph $G_i$ obtained by adding $e_i$ to $G$. It can be proved that the minimum spanning tree $T_i$ of $G_i$ is uniquely determined. Does $T_i$ contain $e_i$? Print the answer as Yes or No.

Note that the queries do not change $T$. In other words, even though Query $i$ considers the graph obtained by adding $e_i$ to $G$, the $G$ in other queries does not have $e_i$.

What is minimum spanning tree? The spanning tree of $G$ is a tree with all of the vertices in $G$ and some of the edges in $G$.
The minimum spanning tree of $G$ is the tree with the minimum total weight of edges among the spanning trees of $G$.

Constraints

• $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)$
• The graph $G$ is connected.
• $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)$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print $Q$ lines. The $i$-th line should contain the answer to Query $i$: Yes or No.

Sample Input 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

Sample Output 1

Yes
No
Yes

Below, let $(u,v,w)$ denote an undirected edge that connects Vertex $u$ and Vertex $v$ and has the weight of $w$. Here is an illustration of $G$:

For example, Query $1$ considers the graph $G_1$ obtained by adding $e_1 = (1,3,1)$ to $G$. The minimum spanning tree $T_1$ of $G_1$ has the edge set $\lbrace (1,2,2),(1,3,1),(2,4,5),(3,5,8) \rbrace$, which contains $e_1$, so Yes should be printed.

Sample Input 2

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

Sample Output 2

Yes
No

update @ 2024/3/10 10:12:23