P10722 [GESP202406 Level 6] Binary Tree

Related multiple-choice and true/false questions: .

Xiao Yang has a binary tree with $n$ nodes, and the root node is labeled $1$. Each node in this binary tree is either white or black. Then Xiao Yang will perform $q$ operations on this binary tree. In each operation, Xiao Yang chooses a node and flips the color of every node in the subtree rooted at that node, meaning black becomes white and white becomes black. Xiao Yang wants to know the color of each node after all $q$ operations are completed.

The first line contains a positive integer $n$, representing the number of nodes in the binary tree. The second line contains $(n-1)$ positive integers. The $i$-th ($1\le i\le n-1$) number indicates the label of the parent of node $(i+1)$. The data guarantees that the tree is a binary tree. The third line contains a $\texttt{01}$ string of length $n$. From left to right, if the $i$-th ($1\le i\le n$) character is $\texttt{0}$, it means node $i$ is white; otherwise, it is black. The fourth line contains a positive integer $q$, representing the number of operations. The next $q$ lines each contain a positive integer $a_i$ ($1\le a_i\le n$), representing the label of the node chosen in the $i$-th operation.

Output a single line containing a $\texttt{01}$ string of length $n$, representing the color of each node after all $q$ operations are completed. From left to right, if the $i$-th ($1\le i\le n$) character is $\texttt{0}$, it means node $i$ is white; otherwise, it is black.

#### Sample Explanation After the first operation, the node colors are: $\texttt{011010}$. After the second operation, the node colors are: $\texttt{000000}$. After the third operation, the node colors are: $\texttt{010000}$. #### Constraints | Subtask ID | Score | $n$ | $q$ | Special Condition | | :--: | :--: | :--: | :--: | :--: | | $1$ | $20$ | $\le 10^5$ | $\le 10^5$ | For all $i\ge 2$, the parent of node $i$ is node $i-1$. | | $2$ | $40$ | $\le 1000$ | $\le 1000$ | | | $3$ | $40$ | $\le 10^5$ | $\le 10^5$ | | For all testdata, it is guaranteed that $n,q\le 10^5$. Translated by ChatGPT 5