Codeforces 429(#245 Div1) A. Xor-tree

問題

n頂点からなる根付き木が与えられる。各頂点は最初0または1である。
このグラフに対して次の操作が好きなだけできる。

操作：好きな頂点vをえらび、vおよび、vの子孫uでdepth(u)-depth(v)が偶数の頂点uの0, 1を反転させる。

最終状態が与えられるとき、その状態にするための操作の回数の最小値を求めよ。

制約条件

n≦10^5

方針

同じ頂点で２度操作をしないとすれば、操作の仕方は一意に定まる。
（根から順に見ていって、最終状態と違うなら反転する）
ので、単にDFSすればいい。

ソースコード

const int MX = 100010;
int n, a[MX], b[MX];
vector<vi> e;

vi ans;

int rec(int c, int p, int flip, int depth){
	
	rep(f, 2){
		if((flip >> depth & 1 ^ f) != (a[c] ^ b[c])) continue;
		int tmp = f;
		if(f) ans.pb(c + 1);
		
		rep(i, e[c].size()) if(e[c][i] != p)
			tmp += rec(e[c][i], c, flip ^ (f << depth), depth ^ 1);
		return tmp;
	}
}

int main(){
	cin >> n;
	e.resize(n);
	rep(i, n - 1){
		int a, b; cin >> a >> b;
		a--; b--;
		e[a].pb(b);
		e[b].pb(a);
	}
	rep(i, n) cin >> a[i];
	rep(i, n) cin >> b[i];
	
	cout << rec(0, 0, 0, 0) << endl;
	rep(i, ans.size()) cout << ans[i] << endl;
	
	return 0;
}