木を道に [yukicoder No.806]

https://yukicoder.me/problems/no/806

解説

https://yukicoder.me/submissions/327823

わかってしまえば簡単な問題。
道を作るということなので、次数が3以上のものはどういう操作を行うにしても、辺を切る必要がある。
切った後は、どこにつなげるかはどうとでもできるので、次数が全部2以下になるように切れれば、
その後は、うまくやって道にできそうな感じがある。
なので、次数が3以上なら2になるように辺を切る回数の総和が答え。

int N; vector<int> E[101010];
//---------------------------------------------------------------------------------------------------
int ans = 0;
void dfs(int cu, int pa = -1) {
    int sz = E[cu].size();
    ans += max(0, sz - 2);
    fore(to, E[cu]) if(to != pa) dfs(to, cu);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N - 1) {
        int a, b; cin >> a >> b;
        a--; b--;
        E[a].push_back(b);
        E[b].push_back(a);
    }

    dfs(0);
    cout << ans << endl;
}