题解 | #小红树上染色#

树形DP分两种状态，当前点不染红则孩子必须染红，当前点染红则孩子可红可白，最后把根节点两种状态相加取模即可。

void solve(){
    int n;cin>>n;
    vvi c(n+1);
    for(int i=1;i<n;++i){
        int u,v;cin>>u>>v;
        c[u].push_back(v);
        c[v].push_back(u);
    }
    vi a(n+1),b,t;
    b.reserve(n);
    t.push_back(1);
    a[1]=-1;
    while(!t.empty()){
        int u=t.back();
        t.pop_back();
        b.push_back(u);
        for(int v:c[u]){
            if(v==a[u])continue;
            a[v]=u;
            t.push_back(v);
        }
    }
    vll x(n+1,1),y(n+1,1);
    for(int i=(int)b.size()-1;i>=0;--i){
        int u=b[i];
        x[u]=1;
        y[u]=1;
        for(int v:c[u]){
            if(v==a[u])continue;
            x[u]=x[u]*y[v]%MOD;
            y[u]=y[u]*(x[v]+y[v])%MOD;
        }
    }
    cout<<(x[1]+y[1])%MOD<<endl;
}