MST边集检查(MST Edge Set Check)

题目描述

本题对应 CSES 3408：MST Edge Set Check。

给定一个包含 $n$ 个顶点、$m$ 条带权无向边的连通图，边的编号为 $1 \sim m$。

接下来有 $q$ 次询问。每次询问给定一个包含 $k$ 条边的边集 $E_j$，请你判断是否存在原图的一棵最小生成树同时包含 $E_j$ 中的所有边。

输入格式

第一行包含三个正整数 $n, m, q$，分别表示顶点数、边数和询问数。

接下来 $m$ 行，第 $i$ 行包含三个正整数 $u_i, v_i, w_i$，表示第 $i$ 条边。

接下来 $q$ 行，每行先给出一个正整数 $k$，随后给出 $k$ 个互不相同的正整数 $e_1, e_2, \dots, e_k$（$1 \le e_i \le m$），表示询问的边编号集合。

输出格式

对于每次询问，若存在同时包含该集合所有边的最小生成树则输出一行 YES，否则输出一行 NO。

样例输入 #1

4 5 3
1 2 2
2 3 2
1 3 2
3 4 3
1 4 4
2 1 2
3 1 2 3
2 1 5

样例输出 #1

YES
NO
NO

数据范围

对于 $100\%$ 的数据，$2 \le n \le 2 \times 10^5$，$n - 1 \le m \le 2 \times 10^5$，$1 \le q \le 2 \times 10^5$，$\sum k \le 2 \times 10^5$，$1 \le w_i \le 10^9$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1900。

测试点分布

出处：原题链接