はまやんはまやんはまやん

hamayanhamayan's blog

Independent Set [Educational DP Contest / DP まとめコンテスト P]

https://atcoder.jp/contests/dp/tasks/dp_p

前提知識

解説

https://atcoder.jp/contests/dp/submissions/3949251

木DPをする。
木上での数え上げといえば木DPを最初に疑って問題ないと思う。
 
隣り合う頂点どおしを黒で塗れないということは、部分木の根の色のみ後々の遷移に関係してくることになる。
dp[cu][c] := 頂点cuを色cで塗ったとき、頂点cuを根とした部分木を塗る組み合わせ
c=0で白、c=1で黒とする。
 
すると、dp[cu][0]は子供の塗られ方はどちらでもいいので、dp[cu][0]はdp[to][0]+dp[to][1]の総積になる。
dp[cu][1]は子供は白しか許されないので、dp[cu][1]はdp[to][0]の総積となる。
すると、dp[0][0]+dp[0][1]が答え。

int N;
vector<int> E[101010];
//---------------------------------------------------------------------------------------------------
mint dp[101010][2];
void dfs(int cu, int pa = -1) {
    dp[cu][0] = dp[cu][1] = 1;
    fore(to, E[cu]) if (to != pa) {
        dfs(to, cu);
        dp[cu][0] *= dp[to][0] + dp[to][1];
        dp[cu][1] *= dp[to][0];
    }
}
//---------------------------------------------------------------------------------------------------
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);
 
    mint ans = dp[0][0] + dp[0][1];
    cout << ans << endl;
}