题解 | 小红树上染色喵

考虑一个点染不同颜色的条件喵

如果这个点是红色，那么她的儿子红白都可以喵

如果这个点是白色，那么她的儿子只能是红色喵

所以只要记录每个子树根节点是红色和白色的方案数，就可以用乘法原理递推喵

于是我们用树形 DP 轻松解决了这题喵，答案就是根的红白方案数之和喵

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

using ll = long long;

const int MOD = 1e9 + 7;

int n;
vector<vector<int>> graph;

pair<ll, ll> Dfs(int x, int fa) {
    pair<ll, ll> res(1, 1);
    auto& [r, w] = res;
    for (const auto& y : graph[x]) {
        if (y != fa) {
            auto&& [a, b] = Dfs(y, x);
            r = r * (a + b) % MOD;
            w = w * a % MOD;
        }
    }
    return res;
}

void Solve() {
    cin >> n;
    graph.resize(n + 1);
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    auto&& [r, w] = Dfs(1, 0);
    cout << (r + w) % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    Solve();
}
// 64 位输出请用 printf("%lld")