⼆叉树

题目描述

⼩杨有⼀棵包含 个节点的⼆叉树，且根节点的编号为 。这棵⼆叉树任意⼀个节点要么是⽩⾊，要么是⿊⾊。之后 ⼩杨会对这棵⼆叉树进⾏ 次操作，每次⼩杨会选择⼀个节点，将以这个节点为根的⼦树内所有节点的颜⾊反转， 即⿊⾊变成⽩⾊，⽩⾊变成⿊⾊。 ⼩杨想知道 次操作全部完成之后每个节点的颜⾊。

输入格式

第⼀⾏⼀个正整数 ，表⽰⼆叉树的节点数量。 第⼆⾏ 个正整数，第 （ ）个数表⽰编号为 的节点的⽗亲节点编号，数据保证是⼀棵⼆叉 树。 第三⾏⼀个长度为 的 串，从左到右第 （ ）位如果为 ，表⽰编号为 的节点颜⾊为⽩⾊，否则为⿊ ⾊。 第四⾏⼀个正整数 ，表⽰操作次数。 接下来 ⾏每⾏⼀个正整数 （ ），表⽰第 次操作选择的节点编号。

输出格式

输出⼀⾏⼀个长度为 的 串，表⽰ 次操作全部完成之后每个节点的颜⾊。从左到右第 （ ） 位如果为 ，表⽰编号为 的节点颜⾊为⽩⾊，否则为⿊⾊。 3.2.4 样例1 1 6 2 3 1 1 3 4 3 100101 4 3 5 1 6 3 7 2 1 010000 3.2.5 样例解释 第⼀次操作后，节点颜⾊为：011010 第⼆次操作后，节点颜⾊为：000000 第三次操作后，节点颜⾊为：010000 3.2.6 数据范围 子任务编号 数据点占比 特殊条件 1 20% 对于所有 ，节点 的⽗亲节点编号为 2 40% 3 40% 对于全部数据，保证有 。 3.2.7 参考程序 1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N = 1e5+10; 4 int n; 5 int son[N][2]; 6 int f[N],col[N],sum[N]; 7 void dfs(int x,int now){ 8 now+=sum[x]; 9 if(now&1)col[x]^=1; 10 for(int i=0;i<2;i++){ 11 if(son[x][i]!=-1)dfs(son[x][i],now); 12 } 13 } 14 int main(){ 15 cin>>n; 16 memset(son,-1,sizeof son); 17 for(int i=2;i<=n;i++){ 18 cin>>f[i]; 19 for(int j=0;j<2;j++){ 20 if(son[f[i]][j]==-1){ 21 son[f[i]][j]=i; 22 break; 23 } 24 } 25 } 26 string s; 27 cin>>s; 28 for(int i=1;i<=n;i++){ 29 col[i]=s[i-1]-'0'; 30 } 31 int q; 32 cin>>q; 33 while(q--){ 34 int x; 35 cin>>x; 36 sum[x]+=1; 37 } 38 39 dfs(1,0); 40 for(int i=1;i<=n;i++){ 41 cout<<col[i]; 42 } 43 cout<<"\n"; 44 }

样例输入 #1

1 6
2 3 1 1 3 4
3 100101
4 3
5 1
6 3
7 2
1 010000

样例输出 #1

样例解释 #1

第⼀次操作后，节点颜⾊为：011010 第⼆次操作后，节点颜⾊为：000000 第三次操作后，节点颜⾊为：010000

数据范围

子任务编号 数据点占比 特殊条件 1 20% 对于所有 ，节点 的⽗亲节点编号为 2 40% 3 40% 对于全部数据，保证有 。

知识点与难度

本题涉及的知识点从属于 GESP 6级，难度等级：⭐⭐⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。