Codeforces #216 Div2. C. Valera and Elections

CF216はDiv2 onlyなので不参加。
http://codeforces.com/contest/369/problem/C

問題

1～N番の番号が振られた点を持つ木構造のグラフが与えられる。
グラフ中、いくつかの辺が破損している。

1番の点をrootとしたとき、グラフのうちある１点を選ぶと、その点からrootにたどるパスに含まれる辺が修理される。
全ての破損した辺を修理するのに、選ぶべき点の数を最少化し、点の選び方の例を示せ。

解法

rootからDFSを行い、途中で破損した辺を通過した場合は、その直後の点の子から1つ以上修理する点があった場合は直後の点は選択不要であり、子に修理する点がなければ直後の点を修理候補とすればよい。

int N;
vector<int> Eok[100001];
vector<int> Eng[100001];
set<int> rep;

bool dpdp(int cur,int pre,bool pro) {
	int i,x;
	bool rp=false;
	
	FOR(i,Eng[cur].size()) if(Eng[cur][i]!=pre) rp |= dpdp(Eng[cur][i],cur,true);
	FOR(i,Eok[cur].size()) if(Eok[cur][i]!=pre) rp |= dpdp(Eok[cur][i],cur,false);
	
	if(!rp && pro) {
		rep.insert(cur+1);
		rp = true;
	}
	return rp;
}


void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y>>f;
		if(f==1) {
			Eok[x-1].push_back(y-1);
			Eok[y-1].push_back(x-1);
		}
		else {
			Eng[x-1].push_back(y-1);
			Eng[y-1].push_back(x-1);
		}
	}
	dpdp(0,-1,false);
	_P("%d\n",rep.size());
	ITR(it,rep) _P("%d ",*it);
	_P("\n");
	
}

まとめ

もう少し簡単に書けたかも。
破損の有無のフラグ管理をミスして何度かWAした。