The Tree
题意翻译
题意:
给定一棵树,维护以下3个操作:
1,1 x表示如果节点x为白色,则将其染黑。否则对这个节点的所有儿子递归进行相同操作
2,2 x表示将以节点x为root的子树染白。
3,3 x表示查询节点x的颜色
输入格式:
第一行n,q两个数表示树的大小和询问个数
第二行n-1个数,第i个数pi表示pi和i之间有一条边
接下来q行,每行2个数,为询问的信息。格式见题意。
题目描述
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.
![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1017G/e1bfda7a1b03fca247e99f6625980764a1349b36.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.Can you help Juliana to process all these queries?
输入输出格式
输入格式
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.
输出格式
For each query of type $ 3 $ , print "black" if the vertex is black; otherwise, print "white".
输入输出样例
输入样例 #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
说明
The first example is shown on the picture below.
![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1017G/cc16931f19a766fcc45c465ac34ccd83cbd711fb.png)The second example is shown on the picture below.
![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1017G/f4ed5ffcf5834fcc15d2af9cfb118e0f9239a3e6.png)