AT_abc287_f [ABC287F] Components 题解
fengenrong
·
·
题解
题意
给你一棵有 N 个节点的树，顶点标号为 1,2,\dots,N ，第 i 条边连接的端点是 a_i,b_i.
对每一个 x=1,2,\dots,N ,解决如下问题:
有 2^N-1 个非空的顶点子集 V ,求 V 的刚好包含 x 个连通块的诱导子图的数量。
什么是诱导子图？
设 S 是图 G 的顶点的子集，S 的诱导子图是包含 S 的所有顶点和这些顶点之间的所有边，这些边的两个端点都必须在 S 中。
思路
不难看出这题是一道树形动态规划，我们可以用 dp(i,j,0) 表示在 i 的子树上有 j 块并且不选第 i 块的方案数，用 dp(i,j,1) 表示在 i 的子树上有 j 块并且选第 i 块的方案数。
由题意得，我们假如不选，则子节点可选可不选。如果选，则子节点要是选则选的块数是一样的，要是不选就要多加一块。
所以，我们可以分三类来讨论：
$$dp(i,j+k,0)= \sum_{x\in ison} dp(i,j,0)\times (dp(x,k,1)+dp(x,k,0))$$
$i$ 点不选则且 $i$ 点的子节点也不选，可得：
$$dp(i,j+k-1,1)= \sum_{x\in ison} dp(i,j,1)\times dp(x,k,1)$$
$i$ 点不选则且 $i$ 点的子节点选，可得：
$$dp(i,j+k,1)= \sum_{x\in ison} dp(i,j,1)\times dp(x,k,0)$$
### 代码
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
struct op {
int from, to, next;//链式前向星
} a[10005];
int head[5005], cnt;
void add(int x, int y) { a[cnt].from = x, a[cnt].to = y, a[cnt].next = head[x], head[x] = cnt++; }//链式前向星存图
const int mod = 998244353;
int son_sum[5005];
int dp[5005][5005][2];
bool vis[5005];
void dfs(int x, int father) {
dp[x][0][0] = dp[x][1][1] = 1;//初始化
son_sum[x] = 1;//初始化
for (int i = head[x]; i != -1; i = a[i].next) {
int y = a[i].to;
if (y == father)
continue;
dfs(y, x);
for (int j = son_sum[x]; j >= 0; j--) {
for (int k = son_sum[y]; k >= 1; k--) {
//根据dp式
dp[x][j + k][0] =
((dp[x][j + k][0]) + ((dp[x][j][0] * ((dp[y][k][1] + dp[y][k][0]) % mod)) % mod)) % mod;
if (j == 0)
continue;
dp[x][j + k][1] = ((dp[x][j + k][1]) + ((dp[x][j][1] * dp[y][k][0]) % mod)) % mod;
dp[x][j + k - 1][1] = ((dp[x][j + k - 1][1]) + ((dp[x][j][1] * dp[y][k][1]) % mod)) % mod;
}
}
son_sum[x] += son_sum[y];//记录当前子树一共有多少个点
}
}
signed main() {
freopen("block.in", "r", stdin);
freopen("block.out", "w", stdout);
memset(head, -1, sizeof(head));
scanf("%lld", &n);
for (int i = 1, x, y; i < n; i++) {
scanf("%lld%lld", &x, &y);
add(x, y), add(y, x);//建边
}
dfs(1, -1);
for (int i = 1; i <= n; i++) {
printf("%lld\n", (dp[1][i][0] + dp[1][i][1]) % mod);//输出答案，记得取模
}
return 0;
}
```