1 条题解

  • 0
    @ 2026-11-12 21:57:50

    [P] Independent Set(dp_p)题解

    题意简述

    NN 个点的树,黑白染色,相邻两点不能同为黑,求方案数  mod 109+7\bmod 10^9+7。

    思路

    状态

    以 11 为根。设

    • fu,0f_{u,0} = uu 染白时,uu 子树的合法染色方案数;
    • fu,1f_{u,1} = uu 染黑时,uu 子树的合法染色方案数。

    转移

    uu 白时,每个孩子可以白也可以黑(彼此独立):

    $$f_{u,0} = \prod_{c \in \text{child}(u)} \left( f_{c,0} + f_{c,1} \right).$$

    uu 黑时,所有孩子必须是白:

    fu,1=∏c∈child(u)fc,0.f_{u,1} = \prod_{c \in \text{child}(u)} f_{c,0}.

    答案 f1,0+f1,1f_{1,0} + f_{1,1}。

    实现细节:避免爆栈

    N≤105N \le 10^5 且可能是链,递归 DFS 会爆栈。做法:先迭代求出 parent 与遍历序 order,再按 order 的逆序自底向上算 ff。

    复杂度

    时间 O(N)O(N),空间 O(N)O(N)。

    参考代码

    #include <cstdio>
    #include <vector>
    using namespace std;
    
    const long long MOD = 1000000007LL;
    
    int main() {
        int n;
        scanf("%d", &n);
        vector<vector<int>> g(n + 1);
        for (int i = 0; i < n - 1; i++) {
            int x, y;
            scanf("%d %d", &x, &y);
            g[x].push_back(y);
            g[y].push_back(x);
        }
        vector<int> parent(n + 1, 0), order;
        vector<char> vis(n + 1, 0);
        vector<int> stk = {1};
        vis[1] = 1;
        while (!stk.empty()) {
            int u = stk.back(); stk.pop_back();
            order.push_back(u);
            for (int v : g[u])
                if (!vis[v]) { vis[v] = 1; parent[v] = u; stk.push_back(v); }
        }
        vector<long long> f0(n + 1, 1), f1(n + 1, 1);
        for (int idx = n - 1; idx >= 0; idx--) {
            int u = order[idx];
            for (int v : g[u])
                if (v != parent[u]) {
                    f0[u] = f0[u] * ((f0[v] + f1[v]) % MOD) % MOD;
                    f1[u] = f1[u] * f0[v] % MOD;
                }
        }
        printf("%lld\n", (f0[1] + f1[1]) % MOD);
        return 0;
    }
    

    易错点

    1. uu 黑时孩子不能黑,所以乘的是 fc,0f_{c,0} 而不是 (fc,0+fc,1)(f_{c,0} + f_{c,1})——这是本题最常见的错。
    2. 迭代 DFS 时用 parent 数组判父,不要用 visited 判重来判断父子(无向树中两者等价,但 parent 更清晰)。
    3. N=1N=1 时答案为 22(白/黑各一种),样例 3 就是。
    4. 每次乘法后取模。

    数据说明

    共 16 组:4 组官方样例;N=1N=1、N=2N=2、N=3N=3 链与星;N=5N=5 星;N=10/100/1000N=10/100/1000 随机树;N=105N=10^5 的链(卡递归爆栈)、星(卡 10510^5 度)、两组随机树。

    • 1

    信息

    ID
    25
    时间
    1000ms
    内存
    256MiB
    难度
    6
    标签
    递交数
    1
    已通过
    1
    上传者