<-- home

AtCoder ABC 036 D

June 23, 2020

D - 塗り絵

条件から与えられるグラフが木であることがわかる。制約を満たすようにノードを白/黒に塗る問題。木DP。

木の再帰的な構造を生かして、DFSしつつ、部分木について根を白/黒に塗る場合の部分木全体の塗り方を求める。

#define MOD 1'000'000'007
using mint = Fp<MOD>;

#define MAX_N 100'000
mint dp[MAX_N][2];
vector<i64> G[MAX_N];
bool seen[MAX_N];

void dfs(i64 u) {
    seen[u] = true;

    mint cntW = 1;
    mint cntB = 1;
    for (i64 v : G[u]) {
        if (seen[v]) continue;
        dfs(v);
        cntW *= (dp[v][0] + dp[v][1]);
        cntB *= dp[v][1];
    }
    dp[u][0] = cntB;
    dp[u][1] = cntW;
}

int main() {
    i64 N; cin >> N;
    REP(i, N - 1) {
        i64 u, v; cin >> u >> v;
        u--, v--;
        G[u].pb(v);
        G[v].pb(u);
    }

    dfs(0);
    cout << (dp[0][0] + dp[0][1]) << endl;

    return 0;
}