ABC 036 D - 塗り絵 ( Tree DP )

D: 塗り絵 - AtCoder Beginner Contest 036 | AtCoder
dp[ u ][ j ] : the number of valid combinations, when now on node u ( not yet colored ), and its father is white / black
dp[ u ][ j ] = product( dp[ v ][ 0 ] ) + product( dp[ v ][ 1 ] ) * ( u can be colored as 1 ) Ɐ v is u's son

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MOD = 1e9 + 7;
typedef long long ll;

int n;
vector< int > G[ MAXN ];
int dp[ MAXN ][ 2 ];

int dfs( int u, int fa, int fc ){
    if( ~dp[ u ][ fc ] ) return dp[ u ][ fc ];
    int w = 1, b = ( fc == -1 || fc == 0 );
    for( int v : G[ u ] ){
        if( v == fa ) continue;
        int wch = dfs( v, u, 0 );
        int bch = dfs( v, u, 1 );
        w = ( (ll)w * wch ) % MOD;
        b = ( (ll)b * bch ) % MOD;
    }
    return ( dp[ u ][ fc ] = w + b ) %= MOD;
}

void solve(){
    memset( dp, -1, sizeof(dp) );
    printf("%d\n", dfs( 1, -1, -1 ));
}

int main(){
    scanf("%d", &n);
    for( int i = 0; i < n - 1; ++i ){
        int u, v; scanf("%d%d", &u, &v);
        G[ u ].push_back( v );
        G[ v ].push_back( u );
    }
    solve();
    return 0;
}