Codeforces Round #245 (Div. 1) A (dfs)

题目
题意: 给定一棵树,权值均为0或1.Now to perform as few operations as possible,Make the weight of each point in the initial tree become the corresponding weight.操作: XOR the weights of a node,and his grandson、Grandchildren's grandchildren all perform XOR operations.
思路: dfs,The number of layers of the current node and the number of flips of nodes at odd layers are additionally maintained、Even number of flips,If the current layer is odd and the odd layer node flips an odd number of times,He also needs to flip.O(1)计算值,Otherwise violence will get stuckO(n^2)
时间复杂度: O(n)
代码:

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n;
int a[N];
int b[N];
vector<int> va[N];
vector<int> res;
void dfs(int cur,int fa,int level,int l,int r) //奇数、偶数
{
    
	if(level&1)
	{
    
		if(l&1) a[cur] ^= 1;
	}
	else
	{
    
		if(r&1) a[cur] ^= 1;
	}
	int ll = l,rr = r;
	if(a[cur]!=b[cur])
	{
    
		if(level&1) ll++;
		else rr++;
		res.push_back(cur);
	}
	for(int i=0;i<va[cur].size();++i)
	{
    
		int j = va[cur][i];
		if(j==fa) continue;
		
		
		dfs(j,cur,level+1,ll,rr);
	}
}
void solve()
{
    
	cin>>n;
	for(int i=0;i<n-1;++i)
	{
    
		int x,y; cin>>x>>y;
		va[x].push_back(y),va[y].push_back(x);
	}
	for(int i=1;i<=n;++i) cin>>a[i];
	for(int i=1;i<=n;++i) cin>>b[i];
	dfs(1,0,0,0,0);
	cout<<res.size()<<"\n";
	for(int i=0;i<res.size();++i)
	{
    
		if(i) cout<<'\n';
		cout<<res[i];
	}
}
signed main(void)
{
    
	solve();
	return 0;
}