A32223. 二叉树题面描述小杨有一棵包含n个节点的二叉树，且根节点的编号为 1 。这棵二叉树任意一个节点要么是白色，要么是黑色。之后小杨会对这棵二叉树进行 次操作，每次小杨会选择一个节点，将以这个节点为根的子树内所有节点的颜色反转， 即黑色变成白色，白色变成黑色。小杨想知道 q 次操作全部完成之后每个节点的颜色。
填空题
困难
知识点
题目描述
二叉树
题面描述
小杨有一棵包含n个节点的二叉树，且根节点的编号为 1 。这棵二叉树任意一个节点要么是白色，要么是黑色。之后小杨会对这棵二叉树进行 次操作，每次小杨会选择一个节点，将以这个节点为根的子树内所有节点的颜色反转， 即黑色变成白色，白色变成黑色。
小杨想知道 q 次操作全部完成之后每个节点的颜色。
输入格式
第一行一个正整数 n，表示二叉树的节点数量。
第二行 n-1 个正整数，第 i（1<=i<=n-1）个数表示编号为i+1 的节点的父亲节点编号，数据保证是一棵二叉树。
第三行一个长度为n的01串，从左到右第i（1<=i<=n-1）位如果为 0，表示编号为 i 的节点颜色为白色，否则为黑色。
第四行一个正整数 q，表示操作次数。
接下来 q 行每行一个正整数 a_i(1<=i<=n），表示第 i 次操作选择的节点编号。
输出格式
输出一行一个长度为n的01串，表示 q 次操作全部完成之后每个节点的颜色。从左到右第 i（1<=i<=n）位如果为0，表示编号为i的节点颜色为白色，否则为黑色。
样例1
输入
6
3 1 1 3 4
100101
3
1
3
2
输出
010000
样例解释
第一次操作后，节点颜色为：011010
第二次操作后，节点颜色为：000000
第三次操作后，节点颜色为：010000
数据范围
对于全部数据，保证有 1<=n， q <=100000 。
参考答案
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10; int n;
int son[N][2];
int f[N],col[N],sum[N];
void dfs(int x,int now) {
now+=sum[x];
if(now&1)col[x]^=1;
for(int i=0; i<2; i++) {
if(son[x][i]!=-1)dfs(son[x][i],now);
}
}
int main() {
cin>>n;
memset(son,-1,sizeof son);
for(int i=2; i<=n; i++) {
cin>>f[i];
for(int j=0; j<2; j++) {
if(son[f[i]][j]==-1) {
son[f[i]][j]=i;
break;
}
}
}
string s;
cin>>s;
for(int i=1; i<=n; i++) {
col[i]=s[i-1]-'0';
}
int q;
cin>>q;
while(q--) {
int x;
cin>>x;
sum[x]+=1;
}
dfs(1,0);
for(int i=1; i<=n; i++) {
cout<<col[i];
}
cout<<"\n";
}
上一题
下一题