← 返回题目列表

Codeforces · 1017/G

G. 树

中文机器翻译题面 查看原题

阿本德森向朱莉安娜分配了一项任务。在此任务中,朱莉安娜有一棵有 $$$n$$$ 个顶点的有根树。顶点号 $$$1$$$ 是这棵树的根。每个顶点可以是黑色或白色。起初,所有顶点都是白色的。朱莉安娜被要求处理 $$$q$$$ 查询。每个查询都是以下三种类型之一:

1. If vertex $$$v$$$ is white, mark it as black;否则,对 $$$v$$$ 的所有直系子代执行此操作。
2. 将$$$v$$$(包括$$$v$$$)子树中的所有顶点标记为白色。
3. 找到第 $$$i$$$ 个顶点的颜色。

操作“1 1”的示例(对应于第一个示例测试)。顶点 $$$1$$$ 和 $$$2$$$ 已经是黑色的,因此操作转到他们的儿子身上。

你能帮助朱莉安娜处理所有这些查询吗?

输入

第一行包含两个整数 $$$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$$$ 个查询的类型和第 $$$i$$$ 个查询的顶点查询。

保证给定的图是一棵树。

输出

对于 $$$3$$$ 类型的每个查询,如果顶点是黑色,则打印“black”;否则,打印“白色”。

示例

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

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

注意

第一个示例如下图所示。

第二个示例如下图所示。