测评会员优惠活动进行中 · 开通 VIP,有效期内测评不限次 VIP 优惠中 · 测评不限次 立即查看

A71621. 二叉树

编程题 基础

题目描述

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

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

输入格式

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

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

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

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

接下来 q 行每行一个正整数 a_i(1 \le a_i \le n),表示第 i 次操作选择的节点编号。

输出格式

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

输入输出样例

输入 #1
6
3 1 1 3 4
100101
3
1
3
2
输出 #1
010000

说明/提示

【样例解释】

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

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

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

【数据范围】

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