dfs40分TLE求调
查看原帖
dfs40分TLE求调
1016101
xiaobeichen楼主2024/9/12 13:47
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e7+5;
int n;
vector<int>tree[N];//tree[i][son]表示节点i的子节点son们
map<int,int>cnt;
bool cl[N];//cl[i]用于存储节点i的颜色 
void dfs(int u){
	cl[u]=!cl[u];//反转颜色(0变1,1变0) 
	for(int v:tree[u]){
		dfs(v);
	} 
} 
int main(){
	int q;
	cin>>n;
	for(int i=1;i<n;i++){
		int fa;
		cin>>fa;
		tree[fa].push_back(i+1);//节点fa添加子节点i+1 
	}
	for(int i=1;i<=n;i++){
		char c;
		cin>>c;
		cl[i]=c-'0';//输入01串 
	}
	cin>>q;
	while(q--){
		int u;
		cin>>u;
		cnt[u]++;
	}
	for(auto time:cnt){
		if(time.second%2!=0)dfs(time.first);
	}
	for(int i=1;i<=n;i++)cout<<cl[i];
	return 0;
}  
2024/9/12 13:47
加载中...