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; }