5463 - GESP:2024-6月等级6-T2-二叉树
Time Limit : 1 秒
Memory Limit : 128 MB
小杨有一棵包含 n个节点的二叉树,且根节点的编号为1 。这棵二叉树任意一个节点要么是白色,要么是黑色。之后小杨会对这棵二叉树进行 q次操作,每次小杨会选择一个节点,将以这个节点为根的子树内所有节点的颜色反转,即黑色变成白色,白色变成黑色。 小杨想知道q次操作全部完成之后每个节点的颜色。
Input
第一行一个正整数n ,表示二叉树的节点数量。 第二行n-1个正整数,第 i(1<=i<=n-1)个数表示编号为i+1 的节点的父亲节点编号,数据保证是一棵二叉树。 第三行一个长度为n的01串,从左到右第 i(1<=i<=n )位如果为0 ,表示编号为i 的节点颜色为白色,否则为黑色。 第四行一个正整数q ,表示操作次数。 接下来q 行每行一个正整数ai (1<=ai<=n ),表示第 i次操作选择的节点编号。
Output
输出一行一个长度为n 的 01串,表示q 次操作全部完成之后每个节点的颜色。从左到右第 i(1<=i<=n ) 位如果为0 ,表示编号为i 的节点颜色为白色,否则为黑色。
Examples
Input
6 3 1 1 3 4 100101 3 1 3 2
Output
010000
Hint
样例解释 第一次操作后,节点颜色为:011010 第二次操作后,节点颜色为:000000 第三次操作后,节点颜色为:010000
对于全部数据,保证有 1<=n,q<=10^5。