1 题意
例题:atcoder dp_p: Independent Set。
给定一棵树,将每个节点染成白色或黑色,要求相邻节点不能同时为黑色。求合法染色方案数,对
把黑色看作选择、白色看作不选,限制与 没有上司的舞会 相同。区别是:舞会求最大收益,本题统计所有合法方案,包括所有节点都不选的方案。
2 状态定义
定义:
| 状态 | 含义 |
|---|---|
状态仍需保留根的颜色,因为它决定父节点能否染黑。同一状态中的不同合法染色都要计入,不能像最优化问题那样只保留收益最大的方案。
3 加法与乘法
3.1 同一孩子相加
若
种选择。
若
3.2 不同孩子相乘
确定
所以,记
加法合并同一子问题的互斥选择,乘法组合不同子问题的独立方案。 不能把舞会公式里的每个 max 都换成加法,却仍然把不同孩子的贡献相加。
4 初值与答案
叶子没有孩子。固定它为白色或黑色后,都恰好有一种染色:
因此在合并孩子前,两个状态都初始化为
根为白色与根为黑色是互斥的两类完整方案,答案为:
注意区分:空集是一种合法方案,方案数为
5 手算示例
以下是自拟示例。节点
| 节点 | 白色 |
黑色 |
|---|---|---|
| 2 | 1 | 1 |
| 3 | 1 | 1 |
| 1 |
当根为白色时,两个叶子各有两种颜色,得到
6 正确性
固定
这建立了方案与各孩子选择组合之间的一一对应。对孩子颜色分类相加、对不同孩子组合相乘,既不遗漏,也不重复。由叶子向根归纳,便能得到全树方案数。
7 代码实现
转移需要先计算孩子。递归写法可以直接放在 DFS 返回时处理,但原题有
下面先用数组记录一个父亲先于孩子的遍历顺序,再倒序计算。这里只要求依赖顺序正确,不要求必须使用递归 DFS。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100000 + 5;
const ll mod = 1000000007;
vector<int> g[maxn];
int fa[maxn], order[maxn];
ll f[maxn][2];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
// 先记录一个父亲先于孩子的顺序,避免长链上的深层递归。
order[1] = 1;
int total = 1;
for (int i = 1; i <= total; ++i) {
int u = order[i];
for (int v : g[u]) {
if (v == fa[u]) continue;
fa[v] = u;
order[++total] = v;
}
}
// 倒序处理,保证孩子的方案数已经算好。
for (int i = total; i >= 1; --i) {
int u = order[i];
f[u][0] = f[u][1] = 1;
for (int v : g[u]) {
if (v == fa[u]) continue;
f[u][0] = f[u][0] * ((f[v][0] + f[v][1]) % mod) % mod;
f[u][1] = f[u][1] * f[v][0] % mod;
}
}
cout << (f[1][0] + f[1][1]) % mod << '\n';
return 0;
}
每次加法和乘法后取模。乘法用 long long,避免两个接近模数的数相乘时溢出 int。时间复杂度为
只统计最优方案
如果题目要求“最大快乐值有多少种实现方式”,就不能统计所有合法方案。需要同时记录最优值与取得该值的方案数。
比较同一孩子的候选状态时,最优值较大者保留其方案数;最优值相等时,将方案数相加。合并不同孩子时,最优值相加,方案数相乘。最优值比较应使用真实值,只有方案数取模。
8 相关题解
暂无相关题解