二叉树

题目描述

小杨有一棵包含 $n$ 个节点的二叉树，且根节点的编号为 $1$。这棵二叉树任意一个节点要么是白色，要么是黑色。之后小杨会对这棵二叉树进行 $q$ 次操作，每次小杨会选择一个节点，将以这个节点为根的子树内所有节点的颜色反转，即黑色变成白色，白色变成黑色。 小杨想知道 $q$ 次操作全部完成之后每个节点的颜色。

输入格式

第一行一个正整数 $n$，表示二叉树的节点数量。 第二行 $n - 1$ 个正整数，第 $i$（$1 \le i \le n - 1$）个数表示编号为 $i + 1$ 的节点的父亲节点编号，数据保证是一棵二叉树。 第三行一个长度为 $n$ 的 01 串，从左到右第 $i$（$1 \le i \le n$）位如果为 $0$，表示编号为 $i$ 的节点颜色为白色，否则为黑色。 第四行一个正整数 $q$，表示操作次数。 接下来 $q$ 行每行一个正整数 $a_i$（$1 \le a_i \le n$），表示第 $i$ 次操作选择的节点编号。

输出格式

输出一行一个长度为 $n$ 的 01 串，表示 $q$ 次操作全部完成之后每个节点的颜色。从左到右第 $i$（$1 \le i \le n$）位如果为 $0$，表示编号为 $i$ 的节点颜色为白色，否则为黑色。

输入样例 1

6
3 1 1 3 4
100101
3
1
3
2

输出样例 1

010000

样例解释 1

第一次操作后，节点颜色为：011010 第二次操作后，节点颜色为：000000 第三次操作后，节点颜色为：010000

数据范围

子任务编号 数据点占比 $n$ $q$ 特殊条件

1 20% $\le 10^5$ $\le 10^5$ 对于所有 $i \ge 2$，节点 $i$ 的父亲节点编号为 $i - 1$
2 40% $\le 1000$ $\le 1000$
3 40% $\le 10^5$ $\le 10^5$

对于全部数据，保证有 $1 \le n, q \le 10^5$。