Codeforces 369(#216 Div2 only) C. Valera and Elections

問題

n個の都市が双方向に通行可能な道路n-1本の道路で結ばれている。
任意の二都市をつなぐパスが存在する。


道路はいくつかが壊れている。
i番の都市を選ぶと、1番の都市からi番の都市へ行くのに必要な道路がすべて修理される。
最低いくつの都市を選べば全ての道路が修理されるか答えよ。

制約条件

n≦10^5

方針

1番の都市を根と考えて、葉から順に選ぶ必要があったら選んでいけばいい。


選ぶ必要がある⇔自分の子孫を選んでない、かつ自分の親へつなぐ道が壊れている

ソースコード

int n;
vector<vector<pi> > e;
vi ans;

int rec(int c, int p){
	
	int res = 0;
	
	rep(i, e[c].size()){
		if(e[c][i].first == p) continue;
		
		int a = rec(e[c][i].first, c);
		
		if(a == 0 && e[c][i].second == 2) res++, ans.pb(e[c][i].first + 1);
		res += a;
	}
	return res;
}

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