问题分析

该问题的核心约束是“不存在两个白色节点相邻”。在图论语境下，如果我们定义被染红的节点集合为 ，那么未被染红的节点（白色节点）集合为 。题目要求 中任意两个节点之间没有边相连，这等价于说 是一个独立集（Independent Set）。

进一步转化，若 是独立集，那么其补集 （即红色节点集合）必须满足：对于树中的每一条边 ，节点 和节点 中至少有一个属于 。这正是点覆盖（Vertex Cover）的定义。因此，本题的本质是：求一棵树中不同点覆盖的方案总数。

树形动态规划 (Tree DP)

由于问题的结构是一棵树，且全局最优解（或方案数）可以通过子树的局部解合并得到，树形动态规划是处理此类计数问题的最优策略。

1. 状态定义

我们需要维护每个节点在不同染色状态下的合法方案数。对于任意节点 ，定义两个状态：

  • ：表示节点 染成白色时，以 为根的子树满足条件的方案数。
  • ：表示节点 染成红色时，以 为根的子树满足条件的方案数。

2. 状态转移方程

对于节点 及其子节点 ：

  • 当 为白色时 ()： 为了满足“不存在两个白色节点相邻”的约束，若父节点 为白色，则其所有子节点 必须染成红色。 因此，方案数为所有子节点在红色状态下的方案数之积：

  • 当 为红色时 ()： 若父节点 为红色，约束已在当前边上得到满足。其子节点 既可以是白色，也可以是红色。 因此，方案数为所有子节点两种状态之和的乘积：

3. 边界条件与初始化

  • 对于叶子节点：
    • （仅染成白色一种方案）
    • （仅染成红色一种方案）
  • 全局初始值为 1（乘法单位元）。

复杂度分析

  • 时间复杂度：

    在树形 DP 中，我们需要通过一次深度优先搜索（DFS）遍历整棵树。每个节点仅被访问一次，每个边缘也仅被访问一次。在每个节点处理状态转移时，其计算复杂度与子节点数量成线性关系。因此，总时间复杂度为 。

  • 空间复杂度：

    我们需要 的空间存储 DP 数组，以及 的空间存储邻接表表示的树结构。在 DFS 递归过程中，递归栈的最大深度在最坏情况下（链状树）为 。

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

static constexpr ll MOD = 1e9 + 7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<vector<ll>> dp(n + 1, vector<ll>(2, 1));
    auto dfs = [&](auto&& self, int u, int p) -> void {
        dp[u][0] = 1;
        dp[u][1] = 1;
        for (int v : adj[u]) {
            if (v == p)
                continue;
            self(self, 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;
        }
    };
    dfs(dfs, 1, -1);

    ll ans = (dp[1][0] + dp[1][1]) % MOD;
    cout << ans << endl;
}