gesp(C++六级)（10）洛谷：P10722：[GESP202406 六级] 二叉树

gesp(C++六级)（10）洛谷：P10722：[GESP202406 六级] 二叉树

题目描述

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

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

输入格式

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

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

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

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

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

输出格式

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

样例 #1

样例输入 #1

6
3 1 1 3 4
100101
3
1
3
2

样例输出 #1

010000

提示

样例解释

第一次操作后，节点颜色为：$\text{011010}$

第二次操作后，节点颜色为：$\text{000000}$

第三次操作后，节点颜色为：$\text{010000}$

数据范围

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

AC代码（100分）

#include<bits/stdc++.h>
using namespace std;
/*思路： 
	计算每个节点的操作次数（子节点的反转次数=父节点的反转次数+自身的反转次数） 
	如果操作次数为偶数，则颜色不变
	如果操作次数为奇数，则颜色反转	 
*/
const int N=1e5+10;
int n,x,q,sum[N],ans[N];
vector<int> v[N];//v[i]存i的所有孩子
char s[N]; 
//dfs函数
void dfs(int x){//计算节点x的答案，然后遍历节点x的所有子节点 
	ans[x]=s[x]-'0';//将节点x的初始状态从字符转化为数字，存到答案数组中 
	if(sum[x]%2==1) ans[x]=1-ans[x];//奇数次反转，偶数次不反转
	for(int i=0;i<v[x].size();i++){//遍历x的所有孩子 
		int z=v[x][i];//子节点 
		sum[z]+=sum[x];//子节点的反转次数=父节点的反转次数+自身的反转次数 
		dfs(z);//深搜子节点 
	} 
} 
int main(){
	cin>>n;
	for(int i=2;i<=n;i++){
		cin>>x;
		v[x].push_back(i);//x是i的父节点 
	} 
	for(int i=1;i<=n;i++) cin>>s[i];//输入字符串 
	cin>>q;//输入操作次数 
	for(int i=1;i<=q;i++){
		int a; 
		cin>>a;
		sum[a]++;//计算每个节点作为父节点的操作次数 
	}
	dfs(1);//1是根节点 
	for(int i=1;i<=n;i++) cout<<ans[i];
	return 0;
}

文末彩蛋：

点击王老师青少年编程主页有更多精彩内容