题解：AT_abc287_f [ABC287F] Components

一个显然的树上背包。

设

dp_{u,k,0/1}

表示以

u

为根的子树中有

k

个连通块，且

u

是否在点集中的方案数。

枚举

u

当前子树的连通块个数

i

，

u

的子节点

v

的连通块个数

j

，转移方程：

$u$ 不选， $v$ 随意： $dp_{u,i+j,0}=dp_{u,i,0} \times (dp_{v,j,0} + dp_{v,j,1})$ 。
$u$ 选， $v$ 不选： $dp_{u,i+j,1} = dp_{u,i,1} \times dp_{v,j,0}$ 。
$u,v$ 都选，此时 $u$ 所在的连通块和 $v$ 所在的连通块组成了一个大连通块： $dp_{u,i+j-1,1} = dp_{u,i,1} \times dp_{v,j,1}$ 。

主要是代码的实现：

只有 $u$ 的子树中至少有一个连通块时才能选 $u$ 本身。
为了避免重算，需要将 $dp_{u}$ 复制到 $t$ 中，将 $dp_u$ 清空，再使用 $t$ 转移 $dp_u$ 。
记得取模。

代码

CPP

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int N = 5050, MOD = 998244353;

int n, dp[N][N][2], t[N][2], sz[N];
vector<int> e[N];

void dfs(int now, int fa){
	sz[now] = 1; dp[now][1][1] = dp[now][0][0] = 1;
	for(int u : e[now]){
		if(u == fa) continue;
		dfs(u, now);
		for(int i = 0; i <= sz[now]; i ++){
			t[i][0] = dp[now][i][0];
			t[i][1] = dp[now][i][1];
			dp[now][i][0] = dp[now][i][1] = 0;
		}
		for(int i = 0; i <= sz[now]; i ++){
			for(int j = 0; j <= sz[u]; j ++){
				dp[now][i + j][0] = (dp[now][i + j][0] + (ll)t[i][0] * dp[u][j][0] % MOD) % MOD;
				if(j > 0) dp[now][i + j][0] = (dp[now][i + j][0] + (ll)t[i][0] * dp[u][j][1] % MOD) % MOD;
				if(i > 0) dp[now][i + j][1] = (dp[now][i + j][1] + (ll)t[i][1] * dp[u][j][0] % MOD) % MOD;
				if(i > 0 && j > 0) dp[now][i + j - 1][1] = (dp[now][i + j - 1][1] + (ll)t[i][1] * dp[u][j][1] % MOD) % MOD;
			}
		}
		sz[now] += sz[u];
	}
}

int main() {
	cin >> n;
	for(int i = 1, u, v; i < n; i ++){
		cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u);
	} 
	dfs(1, 0);
	for(int j = 1; j <= n; j ++)
		cout << (dp[1][j][0] + dp[1][j][1]) % MOD << endl;
    return 0;
}

题解：AT_abc287_f [ABC287F] Components

文章操作

代码

相关推荐

评论

题解：AT_abc287_f [ABC287F] Components