G. Tree Queries

Codeforces

IDCF825G

Time3000ms

Memory256MB

Difficulty—

dfs and similargraphstrees

English · Original

Chinese · Translation

Formal · Original

You are given a tree consisting of _n_ vertices (numbered from 1 to _n_). Initially all vertices are white. You have to process _q_ queries of two different types: 1. 1 _x_ — change the color of vertex _x_ to black. It is guaranteed that the first query will be of this type. 2. 2 _x_ — for the vertex _x_, find the minimum index _y_ such that the vertex with index _y_ belongs to the simple path from _x_ to some black vertex (a simple path never visits any vertex more than once). For each query of type 2 print the answer to it. **Note that the queries are given in modified way**. ## Input The first line contains two numbers _n_ and _q_ (3 ≤ _n_, _q_ ≤ 106). Then _n_ - 1 lines follow, each line containing two numbers _x__i_ and _y__i_ (1 ≤ _x__i_ < _y__i_ ≤ _n_) and representing the edge between vertices _x__i_ and _y__i_. It is guaranteed that these edges form a tree. Then _q_ lines follow. Each line contains two integers _t__i_ and _z__i_, where _t__i_ is the type of _i_th query, and _z__i_ can be used to restore _x__i_ for this query in this way: you have to keep track of the answer to the last query of type 2 (let's call this answer _last_, and initially _last_ = 0); then _x__i_ = (_z__i_ + _last_) _mod_ _n_ + 1. It is guaranteed that the first query is of type 1, and there is at least one query of type 2. ## Output For each query of type 2 output the answer to it. [samples]

给你一棵包含 #cf_span[n] 个顶点的树（编号从 #cf_span[1] 到 #cf_span[n]）。初始时所有顶点均为白色。你需要处理 #cf_span[q] 个两种不同类型的查询：对于每个类型为 #cf_span[2] 的查询，请输出其答案。 *注意：查询是以修改过的方式给出的*。第一行包含两个数 #cf_span[n] 和 #cf_span[q]（#cf_span[3 ≤ n, q ≤ 106]）。接下来 #cf_span[n - 1] 行，每行包含两个数 #cf_span[xi] 和 #cf_span[yi]（#cf_span[1 ≤ xi < yi ≤ n]），表示顶点 #cf_span[xi] 和 #cf_span[yi] 之间的边。保证这些边构成一棵树。接下来 #cf_span[q] 行，每行包含两个整数 #cf_span[ti] 和 #cf_span[zi]，其中 #cf_span[ti] 是第 #cf_span[i] 个查询的类型，而 #cf_span[zi] 可用于恢复该查询中的 #cf_span[xi]：你需要记录上一个类型为 #cf_span[2] 的查询的答案（记作 #cf_span[last]，初始时 #cf_span[last = 0]），然后 #cf_span[xi = (zi + last) mod n + 1]。保证第一个查询是类型 #cf_span[1]，且至少存在一个类型为 #cf_span[2] 的查询。对于每个类型为 #cf_span[2] 的查询，请输出其答案。 ## Input 第一行包含两个数 #cf_span[n] 和 #cf_span[q]（#cf_span[3 ≤ n, q ≤ 106]）。接下来 #cf_span[n - 1] 行，每行包含两个数 #cf_span[xi] 和 #cf_span[yi]（#cf_span[1 ≤ xi < yi ≤ n]），表示顶点 #cf_span[xi] 和 #cf_span[yi] 之间的边。保证这些边构成一棵树。接下来 #cf_span[q] 行，每行包含两个整数 #cf_span[ti] 和 #cf_span[zi]，其中 #cf_span[ti] 是第 #cf_span[i] 个查询的类型，而 #cf_span[zi] 可用于恢复该查询中的 #cf_span[xi]：你需要记录上一个类型为 #cf_span[2] 的查询的答案（记作 #cf_span[last]，初始时 #cf_span[last = 0]），然后 #cf_span[xi = (zi + last) mod n + 1]。保证第一个查询是类型 #cf_span[1]，且至少存在一个类型为 #cf_span[2] 的查询。 ## Output 对于每个类型为 #cf_span[2] 的查询，请输出其答案。 [samples]

**Definitions** Let $ n, q \in \mathbb{Z}^+ $ denote the number of vertices and queries, respectively. Let $ T = (V, E) $ be a tree with vertex set $ V = \{1, 2, \dots, n\} $ and edge set $ E $ of size $ n-1 $. Let $ c: V \to \{0, 1\} $ be a vertex coloring function, where $ c(v) = 0 $ denotes white and $ c(v) = 1 $ denotes black. Initially, $ c(v) = 0 $ for all $ v \in V $. Let $ \text{last} \in \mathbb{Z} $ be a state variable initialized to 0, tracking the answer to the most recent type-2 query. **Constraints** 1. $ 3 \leq n, q \leq 10^6 $ 2. For each edge $ (x_i, y_i) \in E $, $ 1 \leq x_i < y_i \leq n $ 3. For each query $ i \in \{1, \dots, q\} $: - $ t_i \in \{1, 2\} $ - $ z_i \in \mathbb{Z} $, and the actual vertex index is $ x_i = ((z_i + \text{last}) \bmod n) + 1 $ 4. The first query has $ t_1 = 1 $, and at least one query has $ t_i = 2 $ **Objective** Process $ q $ queries: - If $ t_i = 1 $: toggle the color of vertex $ x_i $: $$ c(x_i) \leftarrow 1 - c(x_i) $$ - If $ t_i = 2 $: compute and output the number of edges in $ E $ whose two endpoints have different colors (i.e., the number of bichromatic edges): $$ \text{last} \leftarrow \sum_{(u,v) \in E} \mathbf{1}_{c(u) \ne c(v)} $$ and output $ \text{last} $.

Samples

Input #1

Output #1

3
2
1

API Response (JSON)

{
  "problem": {
    "name": "G. Tree Queries",
    "description": {
      "content": "You are given a tree consisting of _n_ vertices (numbered from 1 to _n_). Initially all vertices are white. You have to process _q_ queries of two different types: 1.  1 _x_ — change the color of ver",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF825G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a tree consisting of _n_ vertices (numbered from 1 to _n_). Initially all vertices are white. You have to process _q_ queries of two different types:\n\n1.  1 _x_ — change the color of ver...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给你一棵包含 #cf_span[n] 个顶点的树（编号从 #cf_span[1] 到 #cf_span[n]）。初始时所有顶点均为白色。你需要处理 #cf_span[q] 个两种不同类型的查询：\n\n对于每个类型为 #cf_span[2] 的查询，请输出其答案。\n\n*注意：查询是以修改过的方式给出的*。\n\n第一行包含两个数 #cf_span[n] 和 #cf_span[q]（#cf_span[3 ≤...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, q \\in \\mathbb{Z}^+ $ denote the number of vertices and queries, respectively.  \nLet $ T = (V, E) $ be a tree with vertex set $ V = \\{1, 2, \\dots, n\\} $ and edge set $ E $ of...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments