C++ 代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
int dp[N][2];
int vis[N];
vector<int>q[N];
int p=1e9+7;
void dfs(int u){
    vis[u]=1;
    for(int i=0;i<q[u].size();i++){
        int j=q[u][i];
        if(vis[j]==0){
            dfs(j);
            dp[u][1]*=dp[j][0];//一般求方案数问题这里都是乘法
            dp[u][1]%=p;       
            dp[u][0]*=dp[j][1]+dp[j][0];
            dp[u][0]%=p;
        }
        else{
            continue;
        }
    }
}
signed main()
{
    int n;
    cin>>n;
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        q[x].push_back(y);
        q[y].push_back(x);
    }
    for(int i=1;i<=n;i++){//注意初始化
        dp[i][0]=1;
        dp[i][1]=1;
    }
    dfs(1);
    cout<<(dp[1][0]+dp[1][1])%p;
    return 0;
}