AtCoder Educational DP Contest P問題解いてみた

今回の問題

問題文

$N$ 頂点の木があります。 頂点には $1, 2, \ldots, N$ と番号が振られています。
各 $i$ ($1 \leq i \leq N-1$) について、$i$ 番目の辺は頂点 $x_i$ と $y_i$ を結んでいます。

太郎君は、各頂点を白または黒で塗ることにしました。
ただし、隣り合う頂点どうしをともに黒で塗ってはいけません。

頂点の色の組合せは何通りでしょうか？
$10^9 + 7$ で割った余りを求めてください。

制約

• 入力はすべて整数である。
• $1 \leq N \leq 10^5$
• $1 \leq x_i, y_i \leq N$
• 与えられるグラフは木である。

自分の回答

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;


vector<vector<int>> adj;

long long dp[100005][2];


void dfs(int u, int p) {
    
    dp[u][0] = 1;
    dp[u][1] = 1;

    for (int v : adj[u]) {
        if (v == p) continue; 
        dfs(v, u);

        
        long long ways_white = (dp[v][0] + dp[v][1]) % MOD;
        dp[u][0] = (dp[u][0] * ways_white) % MOD;
        long long ways_black = dp[v][0];
        dp[u][1] = (dp[u][1] * ways_black) % MOD;
    }
}

int main() {
    int N;
    cin >> N;
    adj.resize(N + 1);
    
    for (int i = 0; i < N - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(1, -1);

    long long ans = (dp[1][0] + dp[1][1]) % MOD;
    
    cout << ans << endl;

    return 0;
}

自分なりの解説

木であることより、メモ化再起で解くことを考えた。dp[i][color]をiをcolorで塗った時のその部分木の場合の数とする。黒と黒は隣接しないように注意するととくことができる。初見で解くことができた。最初葉を探そうとしたが探さなくてもよいことに気が付いた。また、場合の数になるので、足し算でなく掛け算しないといけないことにも注意が必要である。