1 条题解
-
0
[P] Independent Set(dp_p)题解
题意简述
个点的树,黑白染色,相邻两点不能同为黑,求方案数 。
思路
状态
以 为根。设
- = 染白时, 子树的合法染色方案数;
- = 染黑时, 子树的合法染色方案数。
转移
白时,每个孩子可以白也可以黑(彼此独立):
$$f_{u,0} = \prod_{c \in \text{child}(u)} \left( f_{c,0} + f_{c,1} \right).$$黑时,所有孩子必须是白:
答案 。
实现细节:避免爆栈
且可能是链,递归 DFS 会爆栈。做法:先迭代求出
parent与遍历序order,再按order的逆序自底向上算 。复杂度
时间 ,空间 。
参考代码
#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; }易错点
- 黑时孩子不能黑,所以乘的是 而不是 ——这是本题最常见的错。
- 迭代 DFS 时用
parent数组判父,不要用visited判重来判断父子(无向树中两者等价,但parent更清晰)。 - 时答案为 (白/黑各一种),样例 3 就是。
- 每次乘法后取模。
数据说明
共 16 组:4 组官方样例;、、 链与星; 星; 随机树; 的链(卡递归爆栈)、星(卡 度)、两组随机树。
- 1
信息
- ID
- 25
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者