Noelちゃんと木遊び [yukicoder No.763]

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

前提知識

• 木DP

解説

https://yukicoder.me/submissions/307974

木DPをする。
dp[cu][erase] := cu以下の部分木において、頂点cuを消した(erase=1なら消した)ときの木の個数
最初はdp[cu][0] = 1（頂点cu自身）、dp[cu][1]=0（何も無い）とする。
遷移は
dp[cu][0] += max(dp[to][0] - 1, dp[to][1]); // max(頂点toと頂点cuが合体するので-1, 頂点toが無いのでそのまま)
dp[cu][1] += max(dp[to][0], dp[to][1]); // どちらも頂点cuが無いのでそのまま
となる。
max(dp[0][0], dp[0][1])が答え。

int N;
vector<int> E[101010];
//---------------------------------------------------------------------------------------------------
int dp[101010][2];
void dfs(int cu, int pa = -1) {
    dp[cu][0] = 1;
    dp[cu][1] = 0;

    fore(to, E[cu]) if (to != pa) {
        dfs(to, cu);

        dp[cu][0] += max(dp[to][0] - 1, dp[to][1]);
        dp[cu][1] += max(dp[to][0], dp[to][1]);
    }
}
//---------------------------------------------------------------------------------------------------
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 << max(dp[0][0], dp[0][1]) << endl;
}