E. Envy

Codeforces

IDCF892E

Time2000ms

Memory256MB

Difficulty—

graphs

English · Original

Chinese · Translation

Formal · Original

For a connected undirected weighted graph _G_, MST (minimum spanning tree) is a subgraph of _G_ that contains all of _G_'s vertices, is a tree, and sum of its edges is minimum possible. You are given a graph _G_. If you run a MST algorithm on graph it would give you only one MST and it causes other edges to become jealous. You are given some queries, each query contains a set of edges of graph _G_, and you should determine whether there is a MST containing all these edges or not. ## Input The first line contains two integers _n_, _m_ (2 ≤ _n_, _m_ ≤ 5·105, _n_ - 1 ≤ _m_) — the number of vertices and edges in the graph and the number of queries. The _i_\-th of the next _m_ lines contains three integers _u__i_, _v__i_, _w__i_ (_u__i_ ≠ _v__i_, 1 ≤ _w__i_ ≤ 5·105) — the endpoints and weight of the _i_\-th edge. There can be more than one edges between two vertices. It's guaranteed that the given graph is connected. The next line contains a single integer _q_ (1 ≤ _q_ ≤ 5·105) — the number of queries. _q_ lines follow, the _i_\-th of them contains the _i_\-th query. It starts with an integer _k__i_ (1 ≤ _k__i_ ≤ _n_ - 1) — the size of edges subset and continues with _k__i_ distinct space-separated integers from 1 to _m_ — the indices of the edges. It is guaranteed that the sum of _k__i_ for 1 ≤ _i_ ≤ _q_ does not exceed 5·105. ## Output For each query you should print "_YES_" (without quotes) if there's a MST containing these edges and "_NO_" (of course without quotes again) otherwise. [samples] ## Note This is the graph of sample: <center>![image](https://espresso.codeforces.com/adbd629e93f96313d6198b2ec6b671cda2f337f8.png)</center>Weight of minimum spanning tree on this graph is 6. MST with edges (1, 3, 4, 6), contains all of edges from the first query, so answer on the first query is "_YES_". Edges from the second query form a cycle of length 3, so there is no spanning tree including these three edges. Thus, answer is "_NO_".

对于一个连通的无向加权图 #cf_span[G]，最小生成树（MST）是 #cf_span[G] 的一个子图，它包含 #cf_span[G] 的所有顶点，是一棵树，且其边权和最小。你被给定一个图 #cf_span[G]。若对这个图运行 MST 算法，它只会给出一个 MST，并导致其他边变得“嫉妒”。你将收到若干查询，每个查询包含图 #cf_span[G] 中的一组边，你需要判断是否存在一个 MST 包含这些所有边。第一行包含两个整数 #cf_span[n], #cf_span[m] (#cf_span[2 ≤ n, m ≤ 5·105], #cf_span[n - 1 ≤ m]) —— 图的顶点数、边数和查询数。接下来的 #cf_span[m] 行中，第 #cf_span[i] 行包含三个整数 #cf_span[ui], #cf_span[vi], #cf_span[wi] (#cf_span[ui ≠ vi], #cf_span[1 ≤ wi ≤ 5·105]) —— 第 #cf_span[i] 条边的两个端点及其权重。两个顶点之间可能存在多条边。保证给定图是连通的。下一行包含一个整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 5·105]) —— 查询数。接下来 #cf_span[q] 行，第 #cf_span[i] 行是第 #cf_span[i] 个查询。它以一个整数 #cf_span[ki] (#cf_span[1 ≤ ki ≤ n - 1]) 开头，表示边子集的大小，随后是 #cf_span[ki] 个互不相同的、范围在 #cf_span[1] 到 #cf_span[m] 的整数 —— 边的编号。保证所有查询的 #cf_span[ki] 之和不超过 #cf_span[5·105]。对于每个查询，如果存在一个 MST 包含这些边，请输出 "_YES_"（不含引号），否则输出 "_NO_"（同样不含引号）。这是样例的图：该图的最小生成树权重为 #cf_span[6]。包含边 #cf_span[(1, 3, 4, 6)] 的 MST 包含了第一个查询的所有边，因此第一个查询的答案是 "_YES_"。第二个查询中的边构成一个长度为 #cf_span[3] 的环，因此不存在包含这三个边的生成树，故答案为 "_NO_"。 ## Input 第一行包含两个整数 #cf_span[n], #cf_span[m] (#cf_span[2 ≤ n, m ≤ 5·105], #cf_span[n - 1 ≤ m]) —— 图的顶点数、边数和查询数。第 #cf_span[i] 行包含三个整数 #cf_span[ui], #cf_span[vi], #cf_span[wi] (#cf_span[ui ≠ vi], #cf_span[1 ≤ wi ≤ 5·105]) —— 第 #cf_span[i] 条边的两个端点及其权重。两个顶点之间可能存在多条边。保证给定图是连通的。下一行包含一个整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 5·105]) —— 查询数。接下来 #cf_span[q] 行，第 #cf_span[i] 行是第 #cf_span[i] 个查询。它以一个整数 #cf_span[ki] (#cf_span[1 ≤ ki ≤ n - 1]) 开头，表示边子集的大小，随后是 #cf_span[ki] 个互不相同的、范围在 #cf_span[1] 到 #cf_span[m] 的整数 —— 边的编号。保证所有查询的 #cf_span[ki] 之和不超过 #cf_span[5·105]。 ## Output 对于每个查询，如果存在一个 MST 包含这些边，请输出 "_YES_"（不含引号），否则输出 "_NO_"（同样不含引号）。 [samples] ## Note 这是样例的图：该图的最小生成树权重为 #cf_span[6]。包含边 #cf_span[(1, 3, 4, 6)] 的 MST 包含了第一个查询的所有边，因此第一个查询的答案是 "_YES_"。第二个查询中的边构成一个长度为 #cf_span[3] 的环，因此不存在包含这三个边的生成树，故答案为 "_NO_"。

**Definitions** Let $ G = (V, E) $ be a connected undirected weighted graph with $ |V| = n $, $ |E| = m $, and edge weights $ w: E \to \mathbb{Z}^+ $. Let $ \mathcal{M} $ denote the set of all minimum spanning trees (MSTs) of $ G $. **Constraints** 1. $ 2 \leq n, m \leq 5 \cdot 10^5 $, $ n - 1 \leq m $ 2. $ G $ is connected. 3. Edge weights satisfy $ 1 \leq w(e) \leq 5 \cdot 10^5 $. 4. For each query $ i $: - $ 1 \leq k_i \leq n - 1 $ - The query specifies a subset $ Q_i \subseteq E $ of $ k_i $ distinct edges (by index). - $ \sum_{i=1}^{q} k_i \leq 5 \cdot 10^5 $ **Objective** For each query $ Q_i $, determine whether there exists an MST $ T \in \mathcal{M} $ such that $ Q_i \subseteq T $.

Samples

Input #1

Output #1

YES
NO
YES
NO

API Response (JSON)

{
  "problem": {
    "name": "E. Envy",
    "description": {
      "content": "For a connected undirected weighted graph _G_, MST (minimum spanning tree) is a subgraph of _G_ that contains all of _G_'s vertices, is a tree, and sum of its edges is minimum possible. You are given",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF892E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "For a connected undirected weighted graph _G_, MST (minimum spanning tree) is a subgraph of _G_ that contains all of _G_'s vertices, is a tree, and sum of its edges is minimum possible.\n\nYou are given...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "对于一个连通的无向加权图 #cf_span[G]，最小生成树（MST）是 #cf_span[G] 的一个子图，它包含 #cf_span[G] 的所有顶点，是一棵树，且其边权和最小。\n\n你被给定一个图 #cf_span[G]。若对这个图运行 MST 算法，它只会给出一个 MST，并导致其他边变得“嫉妒”。你将收到若干查询，每个查询包含图 #cf_span[G] 中的一组边，你需要判断是否存在一个 M...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ G = (V, E) $ be a connected undirected weighted graph with $ |V| = n $, $ |E| = m $, and edge weights $ w: E \\to \\mathbb{Z}^+ $.  \nLet $ \\mathcal{M} $ denote the set of all min...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments