题解 | 小红树上染色

#include <iostream>
#include <vector>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
vector<vector<int>> dp(2e5, vector<int>(3, 0));
vector<vector<int>> G(2e5, vector<int>());
void dfs(int u, int fa) {
    dp[u][0] = 1;
    dp[u][1] = 1;
    for(int i = 0;i < G[u].size();++i){
        int v = G[u][i];
        if(v == fa) continue;
        dfs(v, u);
        dp[u][0] = (dp[u][0] * dp[v][1]) % mod;
        dp[u][1] = (dp[u][1] * (dp[v][0] + dp[v][1]) % mod) % mod;
    }
}

signed main() {
    int n;
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    dfs(1, -1);

    int ans = (dp[1][0] + dp[1][1]) % mod;
    cout<<ans<<endl;

}
// 64 位输出请用 printf("%lld")