CCCPaste

Untitled

#include 
#include 
//#include 
using namespace std;

const int maxn=1e5+15;
typedef long long ll;
const ll MOD = 1e9 + 7;
vectorg[maxn];
ll dp[maxn][2]; // dp[node][0] -> white color,
//                  dp[node][1] -> black color
void dfs(int node, int par) {
    dp[node][0] = 1;
    dp[node][1] = 1;
    for(int i = 0; i < (int) g[node].size(); i++) {
        int neighbour = g[node][i];
        if(neighbour != par) {
            dfs(neighbour, node);
            
            dp[node][0] *= (dp[neighbour][0] + dp[neighbour][1]) % MOD;
            dp[node][1] *= (dp[neighbour][0]) % MOD;
            
            dp[node][0] %= MOD;
            dp[node][1] %= MOD;
            
        }
    }

}

int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for(int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(0, -1);
    cout << (dp[0][0] + dp[0][1]) % MOD << endl;
    return 0;
}