D-塗り絵

　
D: 塗り絵 - AtCoder Beginner Contest 036 | AtCoder

個の島があり、個の橋がある。
島を白または黒に塗っていく。ただし、両端の島を黒で塗ることはできない。
色の塗り方が何通りあるか求める問題です。

グラフ上の頂点を、黒色で塗るか、白色で塗るかをメモ化再帰で求めていきます。

頂点を で塗ったときの場合の数

とします。（1が白、0が黒）

(1)頂点を白色に塗るとき(はの子の数)

の子は白、黒の2つの色に塗ることができるので

(2)頂点を黒色に塗るとき

の子は白色に塗ることができるので

ただし、が葉となる場合はとします。

#include<bits/stdc++.h>
#define vi vector<int>
#define vvi vector<vector<int> >
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
using ll = long long;
using ld =long double;
#define int ll
#define INF 1e9
#define EPS 0.0000000001
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define all(in) in.begin(), in.end()
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
#define MAX 9999999
using namespace std;
typedef pair<int, int> pii;
typedef pair<int,pii> piii;
#define mp make_pair
int MOD = INF+7;
int memo[100005][2];
vector<vector<int>>edge;

int dfs(int v,int from,int clr){
    if(memo[v][clr]!=INF)return memo[v][clr];
    memo[v][clr]=0;
    bool leaf =  true;
    int value=1;
    rep(i,edge[v].size()){
        int nv=edge[v][i];
        if(nv == from)continue;
        leaf = false;
        if(clr){
            value*=(dfs(nv,v,0)+dfs(nv,v,1));
            value%= MOD;
        }else{
            value*=dfs(nv,v,1);
            value%=(MOD);
        }
    }
    if(leaf)memo[v][clr]=1;
    else memo[v][clr]=value;
    return memo[v][clr];
}
signed main(){
    int n;
    cin>>n;
    edge.resize(n);
    rep(i,n-1){
        int a,b; cin>>a>>b;
        --a,--b;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    rep(i,n)rep(j,2)memo[i][j]=INF;
    cout<<(dfs(0,0,1)+dfs(0,0,0))%(MOD)<<endl;
    
}