TopCoder SRM 583 Div1 Medium TurnOnLamps

さてMedium。途中凡ミスで時間を食ったけど、最終的にきっちり解けたのでまぁ良しとしたい。
http://community.topcoder.com/stat?c=problem_statement&pm=12606

問題

木構造が与えられる。
各辺は、初期状態として0か1の状態が与えられる。
ここで、２つの点を選ぶ、という動作を行うと２点を結ぶ最短経路上の辺の状態が0と1で反転する。

各辺のうち、重要な辺が与えられるので、重要な辺の状態をすべて1にするのに必要な動作の最少回数を答えよ。

解法

この動作の特性を考えると、重要な辺のうちすでに状態が1の辺は、状態を0に戻す必要がないことがわかる。
例えば、以下の構造を考える。辺XYの状態が1で、辺AX・YBの状態が0だとする。

A--X--Y--B

点A-Bに対し動作を行うと、X-Yを跨ぐ他の辺AX・YBの状態を１度に変えられる。
しかし辺X-Yの状態を戻すのにもう1手かかるので、それなら最初か点A-XとY-Bで２手動作を行うのと変わらない。

この事実がわかるとあとはgreedyに行えばよい。
重要なのに状態が0の辺X-Yを見つけたら、その両側で状態が1の辺を通らないようにしつつ状態0の辺をできるだけ取りつくせるように、辺X-Yを含む点A-Bに対し動作を行えばよい。

vector<int> E[60];
int bm[60][60];

int greed(int cur,int pre) {
	int x,tar,ret;
	FOR(x,E[cur].size()) {
		tar=E[cur][x];
		if(tar==pre) continue;
		if(bm[cur][tar]==3) continue;
		if(bm[cur][tar]==2) {
			bm[cur][tar] = bm[tar][cur] = 3;
			greed(tar,cur);
			return 1;
		}
		if(greed(tar,cur) == 1) return 1;
	}
	return 0;
}


class TurnOnLamps {
	int N;
	public:
	int minimize(vector <int> roads, string initState, string isImportant) {
		int i,j,x,y;
		
		N=roads.size()+1;
		FOR(i,N) E[i].clear();
		ZERO(bm);
		FOR(i,N-1) {
			j=(initState[i]-'0') | ((isImportant[i]-'0')<<1);
			E[i+1].push_back(roads[i]);
			E[roads[i]].push_back(i+1);
			bm[i+1][roads[i]] = bm[roads[i]][i+1] = j;
		}
		
		int ret=0;
		int rep=1;
		while(rep) {
			rep=0;
			FOR(x,N) {
				FOR(y,E[x].size()) {
					int tar = E[x][y];
					if(bm[x][tar] == 2) {
						bm[x][tar] = bm[tar][x] = 3;
						greed(x,tar);
						greed(tar,x);
						ret++;
						rep=1;
						goto out;
					}
				}
			}
			out:
			;
		}
		return ret;
		
	}

};

まとめ

こういう木構造のDFS、Codeforcesで慣れた気がするな。