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

题目 题意: 给定一棵树，权值均为0或1。现在要执行尽量少的操作，使得初始树中每个点的权值变为对应权值。操作: 使某个节点的权值进行异或，并且其孙子、孙子的孙子都会进行异或操作。 思路: dfs，额外维护当前节点的层数以及奇数层节点的翻转次数、偶数的翻转次数，如果当前层是奇数并且奇数层节点翻转了奇数次，他也需要翻转。O(1)计算值，否则暴力会卡到O(n^2) 时间复杂度: O(n) 代码:

#include
using namespace std;
const int N = 1e5+10;
int n;
int a[N];
int b[N];
vector va[N];
vector 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>n;
	for(int i=0;i>x>>y;
		va[x].push_back(y),va[y].push_back(x);
	}
	for(int i=1;i>a[i];
	for(int i=1;i>b[i];
	dfs(1,0,0,0,0);
	cout