题解：P10722 [GESP202406 六级] 二叉树

题意

一颗 \(n\) 节点的二叉树，每个节点非黑即白，给你 \(Q\) 次操作，每次给你一个 \(u\)，把 \(u\) 的子树内所有节点颜色反转，问最终每个节点的颜色。

分析

看到数据范围，首先把操作离线。

容易发现如果一个节点重复操作奇数次，等效于操作一次，如果重复操作偶数次，等效于没操作。所以我们可以先把这 \(Q\) 次操作用桶存一下，分别判断操作次数的奇偶性，根据上面的分析，可以同时用另一个桶表示该节点是否被操作。

然后从 \(1\) 号节点开始遍历，因为一个节点的情况只会受其祖先的影响，所以同时用 \(sum\) 记录当前节点的祖先的总操作数，根据奇偶判断当前节点的最终情况，最后输出即可。

一个小细节，每个节点的情况是以字符串形式读入，读入的时候不要读成数字。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
	int w=1,s=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
	while(isdigit(ch)){s=s*10+(ch-'0');ch=getchar();}
	return w*s;
}
const int mod=1e9+7;
const int maxn=1e6+10;
int n,Q;
vector<int> G[maxn];
int d[maxn];
int x[maxn],mp[maxn],y[maxn],tot;
bool f[maxn];
void dfs(int x,int fa,int sum)
{
	int v=0;
	if(y[x])v=1;
	if((sum+v)&1)f[x]=1;
	for(auto y : G[x])
	{
		if(y==fa)continue;
		dfs(y,x,sum+v);
	} 
}
signed main()
{
	cin>>n;
	for(int i=2;i<=n;i++)
	{
		int x=read();
		G[x].push_back(i);
		G[i].push_back(x);
	}
	for(int i=1;i<=n;i++)
	{
		char x;cin>>x;
		d[i]=x-'0';
	}
	Q=read();
	for(int i=1;i<=Q;i++)x[i]=read(),mp[x[i]]++;
	for(int i=1;i<=Q;i++)if(mp[x[i]]&1)y[x[i]]=1;
	dfs(1,0,0);
	for(int i=1;i<=n;i++)cout<<(f[i]?d[i]^1:d[i]);
	return 0;
}