1 条题解
-
0
[V] Subtree(dp_v)题解
题意简述
树上黑白染色,要求黑点集合连通(可全白)。对每个 ,求" 必须为黑"的合法方案数 ( 不一定是素数)。
思路
先算"子树内"的答案
以 为根。设
则
$$d_u = \prod_{c \in \text{child}(u)} \left( 1 + d_c \right),$$其中 表示"孩子子树全白"。
换根:把"父亲一侧"也算进来
设 = "切断 的父边后,父亲一侧全部染黑且与父亲连通(父亲必黑)的方案数"。则
$$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}$$含义:父亲必黑,兄弟子树各自可以全白()或接上父亲(),再往上的部分要么全部白(令父亲为根的整块只有父亲一个黑)——这一项已由""体现——要么继续向上连通。
最终:
(根没有父亲)。
关键:不能求逆元
可能是合数(如 、),除法/逆元不成立。所以兄弟乘积必须用前缀积 × 后缀积。本解对每个顶点,先把它父亲的孩子列表单独收集出来做一次前后缀积,因此整体是 的(若直接对每个孩子遍历全部兄弟,在星形图上会退化为 —— 这是实测会超时的写法)。
复杂度
时间 ,空间 。
参考代码
// 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; }易错点
- 求兄弟积时必须排除父亲(
c != parent[p]),否则父亲会被当成兄弟,链状树上答案直接算错(这是本题最隐蔽的坑)。 - 不能用逆元: 可能不是素数。
- 输出是 行,每行对应一个 。
- 时答案 (只有"1 黑"这一种?注意全白不合法因为 必须黑;所以答案为 )。
- 递归会爆栈(),用迭代序。
数据说明
共 19 组:4 组官方样例(含 的奇偶用例); 边界; 随机(); 随机树三组()、 链与星(,卡排除父亲的逻辑)。
- 求兄弟积时必须排除父亲(
- 1
信息
- ID
- 31
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者