G. The Tree

Codeforces

IDCF1017G

Time3000ms

Memory256MB

Difficulty—

data structures

English · Original

Chinese · Translation

Formal · Original

Abendsen assigned a mission to Juliana. In this mission, Juliana has a rooted tree with $n$ vertices. Vertex number $1$ is the root of this tree. Each vertex can be either black or white. At first, all vertices are white. Juliana is asked to process $q$ queries. Each query is one of three types: 1. If vertex $v$ is white, mark it as black; otherwise, perform this operation on all direct sons of $v$ instead. 2. Mark all vertices in the subtree of $v$ (including $v$) as white. 3. Find the color of the $i$\-th vertex. <center>![image](https://espresso.codeforces.com/9bffe5f40807abebe4823b0f31fb193676eb1484.png) An example of operation "_1 1_" (corresponds to the first example test). The vertices $1$ and $2$ are already black, so the operation goes to their sons instead.</center>Can you help Juliana to process all these queries? ## Input The first line contains two integers $n$ and $q$ ($2\leq n\leq 10^5$, $1\leq q\leq 10^5$) — the number of vertices and the number of queries. The second line contains $n-1$ integers $p_2, p_3, \ldots, p_n$ ($1\leq p_i<i$), where $p_i$ means that there is an edge between vertices $i$ and $p_i$. Each of the next $q$ lines contains two integers $t_i$ and $v_i$ ($1\leq t_i\leq 3$, $1\leq v_i\leq n$) — the type of the $i$\-th query and the vertex of the $i$\-th query. It is guaranteed that the given graph is a tree. ## Output For each query of type $3$, print "_black_" if the vertex is black; otherwise, print "_white_". [samples] ## Note The first example is shown on the picture below. <center>![image](https://espresso.codeforces.com/bf3e3395d6f03ca5d7ee338add41a15cef74d8e2.png)</center>The second example is shown on the picture below. <center>![image](https://espresso.codeforces.com/d5ff2ac61d684a55068b12210fca72fb8b45a8c6.png)</center>

Abendsen 为 Juliana 安排了一项任务。在这项任务中，Juliana 拥有一棵包含 $n$ 个顶点的有根树，顶点编号为 $1$ 的是树的根。每个顶点可以是黑色或白色。最初，所有顶点都是白色的。Juliana 需要处理 $q$ 个查询，每个查询属于以下三种类型之一：你能帮助 Juliana 处理所有这些查询吗？第一行包含两个整数 $n$ 和 $q$（$2 lt.eq n lt.eq 10^5$，$1 lt.eq q lt.eq 10^5$）——顶点数和查询数。第二行包含 $n -1$ 个整数 $p_2, p_3, dots.h, p_n$（$1 lt.eq p_i < i$），其中 $p_i$ 表示顶点 $i$ 和 $p_i$ 之间有一条边。接下来的 $q$ 行中，每行包含两个整数 $t_i$ 和 $v_i$（$1 lt.eq t_i lt.eq 3$，$1 lt.eq v_i lt.eq n$）——第 $i$ 个查询的类型和第 $i$ 个查询的顶点。保证给定的图是一棵树。对于每个类型为 $3$ 的查询，如果该顶点是黑色，则输出 "_black_"；否则输出 "_white_"。第一个示例如下图所示。第二个示例如下图所示。 ## Input 第一行包含两个整数 $n$ 和 $q$（$2 lt.eq n lt.eq 10^5$，$1 lt.eq q lt.eq 10^5$）——顶点数和查询数。第二行包含 $n -1$ 个整数 $p_2, p_3, dots.h, p_n$（$1 lt.eq p_i < i$），其中 $p_i$ 表示顶点 $i$ 和 $p_i$ 之间有一条边。接下来的 $q$ 行中，每行包含两个整数 $t_i$ 和 $v_i$（$1 lt.eq t_i lt.eq 3$，$1 lt.eq v_i lt.eq n$）——第 $i$ 个查询的类型和第 $i$ 个查询的顶点。保证给定的图是一棵树。 ## Output 对于每个类型为 $3$ 的查询，如果该顶点是黑色，则输出 "_black_"；否则输出 "_white_"。 [samples] ## Note 第一个示例如下图所示。第二个示例如下图所示。

**Definitions** Let $ T = (V, E) $ be a rooted tree with $ n $ vertices, where $ V = \{1, 2, \dots, n\} $ and vertex $ 1 $ is the root. Let $ \text{parent}(v) = p_v $ for $ v \in \{2, \dots, n\} $, where $ p_v \in V $ and $ p_v < v $. Let $ c: V \to \{\text{white}, \text{black}\} $ be the color function, initialized as $ c(v) = \text{white} $ for all $ v \in V $. **Constraints** 1. $ 2 \le n \le 10^5 $ 2. $ 1 \le q \le 10^5 $ 3. For each $ v \in \{2, \dots, n\} $, $ 1 \le p_v < v $ 4. For each query $ i \in \{1, \dots, q\} $: - $ t_i \in \{1, 2, 3\} $ - $ v_i \in \{1, \dots, n\} $ **Operations** For each query $ (t_i, v_i) $: - If $ t_i = 1 $: Set $ c(u) = \text{black} $ for all $ u \in \text{subtree}(v_i) $. - If $ t_i = 2 $: Set $ c(u) = \text{white} $ for all $ u \in \text{subtree}(v_i) $. - If $ t_i = 3 $: Output $ c(v_i) $. **Objective** For each query of type $ 3 $, output the current color of vertex $ v_i $.

Samples

Input #1

8 10
1 2 1 2 5 4 5
1 2
3 2
3 1
1 1
1 1
3 5
3 7
3 4
2 2
3 5

Output #1

black
white
black
white
black
white

Input #2

8 11
1 1 2 3 3 6 6
1 1
1 1
1 3
3 2
3 4
3 6
3 7
2 3
1 6
3 7
3 6

Output #2

black
white
black
white
white
black

API Response (JSON)

{
  "problem": {
    "name": "G. The Tree",
    "description": {
      "content": "Abendsen assigned a mission to Juliana. In this mission, Juliana has a rooted tree with $n$ vertices. Vertex number $1$ is the root of this tree. Each vertex can be either black or white. At first, al",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF1017G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Abendsen assigned a mission to Juliana. In this mission, Juliana has a rooted tree with $n$ vertices. Vertex number $1$ is the root of this tree. Each vertex can be either black or white. At first, al...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Abendsen 为 Juliana 安排了一项任务。在这项任务中，Juliana 拥有一棵包含 $n$ 个顶点的有根树，顶点编号为 $1$ 的是树的根。每个顶点可以是黑色或白色。最初，所有顶点都是白色的。Juliana 需要处理 $q$ 个查询，每个查询属于以下三种类型之一：\n\n你能帮助 Juliana 处理所有这些查询吗？\n\n第一行包含两个整数 $n$ 和 $q$（$2 lt.eq n lt....",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T = (V, E) $ be a rooted tree with $ n $ vertices, where $ V = \\{1, 2, \\dots, n\\} $ and vertex $ 1 $ is the root.  \nLet $ \\text{parent}(v) = p_v $ for $ v \\in \\{2, \\dots, n\\} $...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments