1 条题解

  • 0
    @ 2026-11-12 21:58:15

    [V] Subtree(dp_v)题解

    题意简述

    树上黑白染色,要求黑点集合连通(可全白)。对每个 vv,求"vv 必须为黑"的合法方案数  mod M\bmod M(MM 不一定是素数)。

    思路

    先算"子树内"的答案

    以 11 为根。设

    du="u 染黑,且 u 子树内黑点与 u 连通"的方案数.d_u = \text{"$u$ 染黑,且 $u$ 子树内黑点与 $u$ 连通"的方案数}.

    则

    $$d_u = \prod_{c \in \text{child}(u)} \left( 1 + d_c \right),$$

    其中 11 表示"孩子子树全白"。

    换根:把"父亲一侧"也算进来

    设 wuw_u = "切断 uu 的父边后,父亲一侧全部染黑且与父亲连通(父亲必黑)的方案数"。则

    $$w_u = \left( \prod_{\text{sibling } s \text{ of } u} (1 + d_s) \right) \times \begin{cases} 1, & \text{parent}(u) = 1,\\ 1 + w_{\text{parent}(u)}, & \text{否则}. \end{cases}$$

    含义:父亲必黑,兄弟子树各自可以全白(11)或接上父亲(dsd_s),再往上的部分要么全部白(令父亲为根的整块只有父亲一个黑)——这一项已由"1+1+"体现——要么继续向上连通。

    最终:

    ansv=dv×(1+wv),\text{ans}_v = d_v \times \left( 1 + w_v \right),

    w1=0w_1 = 0(根没有父亲)。

    关键:不能求逆元

    MM 可能是合数(如 M=6M=6、M=109M=10^9),除法/逆元不成立。所以兄弟乘积必须用前缀积 × 后缀积。本解对每个顶点,先把它父亲的孩子列表单独收集出来做一次前后缀积,因此整体是 O(N)O(N) 的(若直接对每个孩子遍历全部兄弟,在星形图上会退化为 O(N2)O(N^2) —— 这是实测会超时的写法)。

    复杂度

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

    参考代码

    // dp_v Subtree: 换根 DP,M 不一定是素数 -> 用前缀/后缀乘积求兄弟积,不用逆元
    // d[u]  : u 染黑、u 子树内黑点与 u 连通(孩子子树全白或接上 u)的方案数
    //         d[u] = prod over child c (1 + d[c])
    // w[u]  : 切断 u 的父边后,"父亲一侧"父亲必黑且连通的方案数
    //         w[u] = (prod over sibling s of (1+d[s])) * (p==1 ? 1 : 1 + w[p])
    // ans[v]= d[v] * (1 + w[v])       (v 为根时 ans = d[v])
    // 兄弟积用"每个父亲的孩子列表做一次前后缀乘积",总 O(N)
    #include <cstdio>
    #include <vector>
    using namespace std;
    
    int main() {
        int n;
        long long M;
        if (scanf("%d %lld", &n, &M) != 2) return 0;
        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;
        order.reserve(n);
        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); }
        }
        // d: 逆序自底向上
        vector<long long> d(n + 1, 1), w(n + 1, 0);
        for (int idx = n - 1; idx >= 0; idx--) {
            int u = order[idx];
            for (int v : g[u])
                if (v != parent[u]) d[u] = d[u] * ((1 + d[v]) % M) % M;
        }
        // 兄弟积 pre/suf:对每个顶点 p 的孩子列表只做一次前缀积/后缀积
        // rowPre[u] 存储"u 在父亲孩子列表中的前缀积"与"后缀积"
        vector<long long> pre(n + 1, 1), suf(n + 1, 1);
        for (int idx = 0; idx < n; idx++) {
            int p = order[idx];
            // 只处理以 p 为父亲的孩子
            vector<int> kids;
            for (int v : g[p])
                if (v != parent[p]) kids.push_back(v);
            int m = (int)kids.size();
            long long acc = 1;
            for (int i = 0; i < m; i++) {
                pre[kids[i]] = acc;
                acc = acc * ((1 + d[kids[i]]) % M) % M;
            }
            acc = 1;
            for (int i = m - 1; i >= 0; i--) {
                suf[kids[i]] = acc;
                acc = acc * ((1 + d[kids[i]]) % M) % M;
            }
            // 正序算 w(父亲的 w 已算好)
            for (int c : kids) {
                long long sib = pre[c] * suf[c] % M;
                long long upper = (p == 1) ? 1 : ((1 + w[p]) % M);
                w[c] = sib * upper % M;
            }
        }
        for (int v = 1; v <= n; v++) {
            long long ans = d[v];
            if (v != 1) ans = ans * ((1 + w[v]) % M) % M;
            printf("%lld
    ", ans);
        }
        return 0;
    }
    

    易错点

    1. 求兄弟积时必须排除父亲(c != parent[p]),否则父亲会被当成兄弟,链状树上答案直接算错(这是本题最隐蔽的坑)。
    2. 不能用逆元:MM 可能不是素数。
    3. 输出是 NN 行,每行对应一个 vv。
    4. N=1N=1 时答案 11(只有"1 黑"这一种?注意全白不合法因为 vv 必须黑;所以答案为 11)。
    5. 递归会爆栈(N=105N=10^5),用迭代序。

    数据说明

    共 19 组:4 组官方样例(含 M=2M=2 的奇偶用例);N=1,2,3,4N=1,2,3,4 边界;N=6/20/50/100/1000N=6/20/50/100/1000 随机(M=100,2,999999937,109M=100,2,999999937,10^9);N=105N=10^5 随机树三组(M=2,109,999999937M=2,10^9,999999937)、N=105N=10^5 链与星(M=6M=6,卡排除父亲的逻辑)。

    • 1

    信息

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