CF1017G The Tree

题目描述

Abendsen 给 Juliana 分配了一个任务。在这个任务中，Juliana 有一棵包含 $n$ 个结点的有根树，结点编号为 $1$ 的结点是树的根。每个结点可以是黑色或白色。最开始，所有结点都是白色的。Juliana 需要处理 $q$ 个操作。每个操作有三种类型：

1. 如果结点 $v$ 是白色的，将其标记为黑色；否则，对 $v$ 的所有直接儿子执行此操作。
2. 将以 $v$ 为根的子树中的所有结点（包括 $v$ 本身）都标记为白色。
3. 查询第 $i$ 个结点的颜色。

如下图所示，是操作 “1 1” 的示例（对应第一个样例测试）。结点 $1$ 和 $2$ 已经是黑色，因此该操作会递归作用于它们的儿子。你能帮助 Juliana 处理所有这些操作吗？

输入格式

第一行包含两个整数 $n$ 和 $q$（$2\leq n\leq 10^5$，$1\leq q\leq 10^5$），分别表示结点数和操作数。

第二行包含 $n-1$ 个整数 $p_2, p_3, \ldots, p_n$（$1\leq p_i<i$），其中 $p_i$ 表示存在一条连接结点 $i$ 和 $p_i$ 的边。

接下来的 $q$ 行，每行包含两个整数 $t_i$ 和 $v_i$（$1\leq t_i\leq 3$，$1\leq v_i\leq n$），表示第 $i$ 次操作的类型和对应的结点编号。

保证给定的图是一棵树。

输出格式

对于每个类型为 $3$ 的操作，如果该结点是黑色，输出 "black"；否则输出 "white"。

输入输出样例 #1

输入 #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

输出 #1

black
white
black
white
black
white

输入输出样例 #2

输入 #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

输出 #2

black
white
black
white
white
black

说明/提示

第一个样例如下图所示。

第二个样例如图所示。

由 ChatGPT 4.1 翻译