A66701 | 二叉树

3.2 编程题 2 

试题名称：二叉树 

时间限制：1.0 s 

内存限制：512.0 MB 

3.2.1 题面描述 

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

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

3.2.2 输入格式 

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

第二行n-1个正整数，第i（1≤i≤n-1）个数表示编号为i+1的节点的父亲节点编号，数据保证是一棵二叉树。 

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

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

接下来q行每行一个正整数a_i（1≤a_i≤n），表示第i次操作选择的节点编号。 

3.2.3 输出格式 

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

3.2.4 样例1 

3.2.5 样例解释 

第一次操作后，节点颜色为：011010 

第二次操作后，节点颜色为：000000 

第三次操作后，节点颜色为：010000 

3.2.6 数据范围 

对于全部数据，保证有1≤n,q≤10⁵。