树的覆盖
\(dp_{i,j,0/1/2}\) 表示以 \(i\) 为根的子树中覆盖 \(j\) 个点的方案数。其中 \(0/1/2\) 分别表示了 \(3\) 种情况。
- \(0\) 表示示当前节点和子节点都没被选中
- \(1\) 表示当前节点被选中,子节点选中与不选中都归于这一类
- \(2\) 表示存在子节点被选中且当前节点不选中
考虑 \(\rm dp\) 转移
枚举已遍历子树中选择几个,再枚举正在遍历的子树中选择几个,根据乘法原理相乘即可。
核心代码:
for (auto v : E[x]) {
if (v == fa) continue;
dfs(v, x);
R(i, 0, sz[x]) {
R(j, 0, sz[v]) {
R(t1, 0, 2) {
R(t2, 0, 2) {
int sum = i + j, p = t1;
if (!t1 && t2 == 1) p = 2, ++sum;
if (t1 == 1 && !t2) ++sum;
tmp[sum][p] += dp[x][i][t1] * dp[v][j][t2];
tmp[sum][p] %= P;
}
}
}
}
sz[x] += sz[v];
R(i, 0, sz[x]) {
R(j, 0, 2) {
dp[x][i][j] = tmp[i][j];
tmp[i][j] = 0;
}
}
}
其中 \(sum\) 表示在已遍历子树与正在遍历的子树的选择下会在 \(x\) 的子树中覆盖几个点。
在这里你会发现一些变化,if (!t1 && t2 == 1) p = 2, ++sum;
!t1
的意思是 \(x\) 不选且它没有儿子选中,然而 t2==1
的意思是 \(x\) 的正在遍历的点要选,所以两个状态矛盾,现在的状态变为了 \(x\) 不选且它有儿子要选,变为状态 \(2\)。两个 ++sum
的意思是有一个点选了而它相邻的点没选,所以覆盖的总数要 \(+1\)。
还有一个细节,代码中用了一个临时数组来存储当前的 \(dp\),否则会用到现在的信息就会发生错误。
几乎完整的代码:
const int N = 2005, P = 1e9 + 7;
int n, sz[N], dp[N][N][3], tmp[N][3];
vector <int> E[N];
void dfs(int x, int fa) {
sz[x] = 1;
dp[x][1][1] = dp[x][0][0] = 1;
for (auto v : E[x]) {
if (v == fa) continue;
dfs(v, x);
R(i, 0, sz[x]) {
R(j, 0, sz[v]) {
R(t1, 0, 2) {
R(t2, 0, 2) {
int sum = i + j, p = t1;
if (!t1 && t2 == 1) p = 2, ++sum;
if (t1 == 1 && !t2) ++sum;
tmp[sum][p] += dp[x][i][t1] * dp[v][j][t2];
tmp[sum][p] %= P;
}
}
}
}
sz[x] += sz[v];
R(i, 0, sz[x]) {
R(j, 0, 2) {
dp[x][i][j] = tmp[i][j];
tmp[i][j] = 0;
}
}
}
}
signed main() {
read(n);
R(i, 1, n - 1) {
int u, v;
read(u, v);
E[u].pb(v), E[v].pb(u);
}
dfs(1, 0);
int ans = 0;
R(i, 0, n) {
ans = dp[1][i][0] + dp[1][i][1] + dp[1][i][2]; ans %= P;
write(ans), ptc('\n');
}
return 0;
}
标签:tmp,sz,14,题解,sum,t2,t1,2022.11,dp
From: https://www.cnblogs.com/cyyhcyyh/p/16895360.html