题解 | 小红树上染色

dfs+线性dp

从1开始做dfs，初始化dp[i][0],dp[i][1]为1

dp[i][0]表示i节点,不染色的方案数

观察得到dp方程如下：

dp[i][1] =dp[i][1]*((dp[j][1]%mod+dp[j][0]%mod)%mod)%mod;

dp[i][0] = (dp[i][0]*dp[j][1]%mod)%mod;

#include <iostream>
#include <vector>
using namespace std;

const long long mod = 1e9 + 7;
int n;
vector<int> rt[100005];
long long dp[100005][2];
bool vst[100005];

void dfs(int i) {
    vst[i] = true;
    int ret = 0;
    for (int j : rt[i]) {
        if (vst[j]) continue;
        dfs(j);
        dp[i][1] =dp[i][1]*((dp[j][1]%mod+dp[j][0]%mod)%mod)%mod;
        dp[i][0] = (dp[i][0]*dp[j][1]%mod)%mod;
        ret = 1;
    }
}

int main() {
    cin >> n;
    for(int i=1;i<=n;i++){
        dp[i][1]=1;
        dp[i][0]=1;
    }
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        rt[u].push_back(v);
        rt[v].push_back(u);
    }
    dfs(1);
    cout << (dp[1][0] + dp[1][1]) % mod;
}