Codeforces #245 Div1 A. Xor-tree

適当解法が２つも通ってしまい、ABCDが通って自己ベスト順位＋赤突入しました。
http://codeforces.com/contest/429/problem/A

問題

根付き木が与えられる。
各頂点は初期値として0または1が与えられ、また目標値が同様に0,1が与えられる。
この木において処理を施し、初期値を目標値にしたい。

この時、以下のような数値の変更処理を行うことができる。

• 任意の頂点を選択すると、その頂点のサブツリーのうち、その頂点からの距離が偶数の頂点の0,1を反転する。

初期値を目標値にするために必要な、上記処理の最小回数と対象の頂点を求めよ。

解法

ある頂点の処理はサブツリーには影響しても祖先には影響しない。
よって、根から順に初期値を目標値にするのに必要なら適宜反転を行いつつ、DFSを行えばよい。
その際、根から偶数距離の頂点の反転の有無と奇数距離の頂点の反転の有無を保持しながら処理していく。

int N;
vector<int> E[100005];
int S[1000001];
int T[1000001];
vector<int> R;

void dfs(int cur,int pre,int f1,int f2) {
	if(S[cur]^f1!=T[cur]) {
		f1^=1;
		R.push_back(cur+1);
	}
	
	int i;
	FOR(i,E[cur].size()) {
		int tar=E[cur][i];
		if(tar==pre) continue;
		dfs(tar,cur,f2,f1);
	}
}


void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	FOR(i,N) cin>>S[i];
	FOR(i,N) cin>>T[i];
	
	dfs(0,-1,0,0);
	_P("%d\n",R.size());
	FOR(i,R.size()) _P("%d\n",R[i]);
}

まとめ

Aからツリーとは面倒な問題。
最速の人も4:30程度かかり、自分も6分かかった。
でもすんなり解けてよかった。