31 October

https://www.cnblogs.com/RabbitHu/p/51nod1353.html

树形 DP 求所有联通块 \(\ge K\) 的方案数.

切断：\(\forall i\in\left[1, s_u\right]\), \(\displaystyle f(u, i) =\sum_{j=1}^{s_v} f(v, j) =f(v, 0)\).

不切断：\(\forall i\in\left[1, s_u\right]\), \(\displaystyle \sum_{j=1}^{s_v}f(u, i+j) = f(u, i) f(v, j)\).

void dfs(int u, int pre) {

	dp[u][1]=sz[u]=1;

	for (int k=head[u], v; k; k=nex[k]) if (v=to[k]!=pre) {

		dfs(v, u);

		for (int i=sz[u]; i; --i) {

			for (int j=1; j<=sz[v]; ++j) dp[u][i+j] = (dp[u][i+j] + dp[u][i]*dp[v][j])%mod;

			dp[u][i]=dp[u][i]*dp[v][0]%mod;

		}

		sz[u]+=sz[v];

	}

	for (int i=K; i<=sz[u]; ++i) dp[u][0]=(dp[u][0]+dp[u][i])%mod;

}

dfs(1, 0);

for (int i=K; i<=sz[i]; ++i) ans=(ans+dp[1][i])%mod;

巴特西

31 October

最新文章

热门文章