题解 | 小红树上染色

#include<iostream>
#include<vector>
using namespace std;
const int mod(1e9 + 7);
vector<vector<int>> rec;
pair<long long int, long long int>dfs(int u,int i){
    long long red = 1;
    long long white = 1;
    for(int v:rec[u]){
        if(v==i){
            continue;
        }auto [red2,white2] = dfs(v,u);
        red = red*(red2+white2) % mod;
        white = white*red2 % mod;
    }return {red,white};
}int main(){
    int n;
    cin>>n;
    rec.resize(n+1);
    for(int i=0;i<n-1;i++){
        int u,v;
        cin>>u>>v;
        rec[u].push_back(v);
        rec[v].push_back(u);
    }
    auto[red,white] = dfs(1,-1);
    long long int res= (red+white)%mod;
    cout<<res<<endl;
    return 0;
}