#G1054. [GESP202406 六级] 二叉树

[GESP202406 六级] 二叉树

[GESP202406 六级] 二叉树

题目描述

小杨有一棵包含 nn 个节点的二叉树,且根节点的编号为 11。这棵二叉树任意一个节点要么是白色,要么是黑色。之后小杨会对这棵二叉树进行 qq 次操作,每次小杨会选择一个节点,将以这个节点为根的子树内所有节点的颜色反转,即黑色变成白色,白色变成黑色。

小杨想知道 qq 次操作全部完成之后每个节点的颜色。

输入格式

第一行一个正整数 nn,表示二叉树的节点数量。

第二行 n−1n-1 个正整数,第 ii(1≤i≤n−11 ≤ i ≤ n-1)个数表示编号为 i+1i+1 的节点的父亲节点编号,数据保证是一棵二叉树。

第三行一个长度为 nn 的 01 串,从左到右第 ii(1≤i≤n1 ≤ i ≤ n)位如果为 0,表示编号为 ii 的节点颜色为白色,否则为黑色。

第四行一个正整数 qq,表示操作次数。

接下来 qq 行每行一个正整数 aia_i(1≤ai≤n1 ≤ a_i ≤ n),表示第 ii 次操作选择的节点编号。

输出格式

输出一行一个长度为 nn 的 01 串,表示 qq 次操作全部完成之后每个节点的颜色。从左到右第 ii(1≤i≤n1 ≤ i ≤ n)位如果为 0,表示编号为 ii 的节点颜色为白色,否则为黑色。

样例 #1

样例输入 #1

6
3 1 1 3 4
100101
3
1
3
2

样例输出 #1

010000

样例解释

第一次操作后,节点颜色为:011010

第二次操作后,节点颜色为:000000

第三次操作后,节点颜色为:010000

数据范围

子任务编号 数据点占比 nn qq 特殊条件
1 20% ≤105≤ 10^5 对于所有 i≥2i ≥ 2,节点 ii 的父亲节点编号为 i−1i-1
2 40% ≤1000≤ 1000 无
3 ≤105≤ 10^5
  • 对于全部数据,保证有 1≤n,q≤1051 ≤ n, q ≤ 10^5。