10669: 洛谷P10722 - [GESP六级] [202406]二叉树
[Creator : ]
Description
小杨有⼀棵包含 $n$ 个节点的二叉树,且根节点的编号为 $1$。这棵二叉树任意⼀个节点要么是白色,要么是黑色。之后小杨会对这棵二叉树进行 $q$ 次操作,每次小杨会选择⼀个节点,将以这个节点为根的子树内所有节点的颜色反转,即黑色变成白色,白色变成黑色。
小杨想知道 $q$ 次操作全部完成之后每个节点的颜色。
小杨想知道 $q$ 次操作全部完成之后每个节点的颜色。
Input
第⼀行一个正整数 $n$,表示二叉树的节点数量。
第二行 $(n-1)$ 个正整数,第 $i$($1\le i\le n-1$)个数表示编号为 $(i+1)$ 的节点的父亲节点编号,数据保证是⼀棵二叉树。
第三行一个长度为 $n$ 的 $\texttt{01}$ 串,从左到右第 $i$($1\le i\le n$)位如果为 $\texttt{0}$,表示编号为 $i$ 的节点颜色为白色,否则为黑色。
第四行⼀个正整数 $q$,表示操作次数。
接下来 $q$ 行每行⼀个正整数 $a_i$($1\le a_i\le n$),表示第 $i$ 次操作选择的节点编号。
第二行 $(n-1)$ 个正整数,第 $i$($1\le i\le n-1$)个数表示编号为 $(i+1)$ 的节点的父亲节点编号,数据保证是⼀棵二叉树。
第三行一个长度为 $n$ 的 $\texttt{01}$ 串,从左到右第 $i$($1\le i\le n$)位如果为 $\texttt{0}$,表示编号为 $i$ 的节点颜色为白色,否则为黑色。
第四行⼀个正整数 $q$,表示操作次数。
接下来 $q$ 行每行⼀个正整数 $a_i$($1\le a_i\le n$),表示第 $i$ 次操作选择的节点编号。
Output
输出一行一个长度为 $n$ 的 $\texttt{01}$ 串,表示 $q$ 次操作全部完成之后每个节点的颜色。从左到右第 $i$($1\le i\le n$) 位如果为 $\texttt{0}$,表示编号为 $i$ 的节点颜色为白色,否则为黑色。
Constraints
对于全部数据,保证有 $n,q\le 10^5$。
Sample 1 Input
6
3 1 1 3 4
100101
3
1
3
2
Sample 1 Output
010000
第一次操作后,节点颜色为:$\texttt{011010}$
第二次操作后,节点颜色为:$\texttt{000000}$
第三次操作后,节点颜色为:$\texttt{010000}$
第二次操作后,节点颜色为:$\texttt{000000}$
第三次操作后,节点颜色为:$\texttt{010000}$