Background

Related multiple-choice and true/false questions: https://ti.luogu.com.cn/problemset/1154.

Problem Description

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.

Input Format

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 Format

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.

6
3 1 1 3 4
100101
3
1
3
2

010000

Hint

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

For all testdata, it is guaranteed that $n,q\le 10^5$.

Translated by ChatGPT 5