2019.02.07 bzoj4784: [Zjoi2017]仙人掌（仙人掌+树形dp）

传送门

题意：给一个无向连通图，问给它加边形成仙人掌的方案数。

思路：

先考虑给一棵树加边形成仙人掌的方案数。

这个显然可以做树形dp。

fif_ifi表示把iii为根的子树加边形成仙人掌的方案数。

然后有两种情况：

iii点没有父亲
iii点有父亲

对于第一种情况即iii是树根的情况，显然fi=(∏fv)∗g∣sonp∣f_i=(\prod f_v)*g_{|son_p|}fi=(∏fv)∗g∣sonp∣，其中gig_igi表示给iii个儿子两两配对（每个儿子可配可不配的方案数）。

对于第二种情况有可能把iii跟父亲连上的那条边拿来放进一个环里，因此把iii也看成一个允许配对的连通块即可，则fi=(∏fv)∗g∣sonp∣+1f_i=(\prod f_v)*g_{|son_p|+1}fi=(∏fv)∗g∣sonp∣+1

现在只需要预处理出ggg数组即可，我们再次用dpdpdp解决这个问题：

g0=g1=1,gi=gi−1+(i−1)gi−2,(i≥2)g_0=g_1=1,g_i=g_{i-1}+(i-1)g_{i-2},(i\ge2)g0=g1=1,gi=gi−1+(i−1)gi−2,(i≥2)

这个递推很简单。

于是我们就成功处理出了树的情况，现在只用考虑原图怎么搞。

原图不是一个仙人掌，puts(0)puts(0)puts(0)即可
原图是一个仙人掌，我们把所有在环上面的边都删掉就成了一个森林，把每棵树的方案数统计出来乘起来就是答案。

代码：

#include<bits/stdc++.h>
#define ri register int
using namespace std;
inline int read(){
	int ans=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
	return ans;
}
const int N=5e5+5,mod=998244353;
typedef long long ll;
inline int add(const int&a,const int&b){return a+b>=mod?a+b-mod:a+b;}
inline int dec(const int&a,const int&b){return a>=b?a-b:a-b+mod;}
inline int mul(const int&a,const int&b){return (ll)a*b%mod;}
int n,m,dfn[N],low[N],tot=0,cnt[N],g[N],f[N],fa[N],siz;
bool vis[N],flag;
vector<int>e[N];
map<int,int>ban[N];
inline void solve(int rt,int p){
	ban[rt][p]=ban[p][rt]=1;
	while(p!=rt){
		if(++cnt[p]==2){flag=0;return;}
		ban[p][fa[p]]=ban[fa[p]][p]=1,p=fa[p];
	}
}
void tarjan(int p){
	++siz;
	if(!flag)return;
	dfn[p]=low[p]=++tot;
	for(ri i=0,v;i<e[p].size();++i){
		if((v=e[p][i])==fa[p])continue;
		if(!flag)return;
		if(!dfn[v])fa[v]=p,tarjan(v),low[p]=min(low[p],low[v]);
		else low[p]=min(low[p],low[v]);
	}
	if(!flag)return;
	for(ri i=0,v;i<e[p].size();++i)if(fa[v=e[p][i]]!=p&&dfn[p]<dfn[v])solve(p,v);
}
void dfs(int p,int fat){
	vis[p]=1;
	int du=0,mult=1;
	for(ri i=0,v;i<e[p].size();++i){
		if((v=e[p][i])==fat||ban[p][v])continue;
		dfs(v,p),mult=mul(mult,f[v]),++du;
	}
	if(fat)f[p]=mul(mult,g[du+1]);
	else f[p]=mul(mult,g[du]);
}
int main(){
	g[0]=g[1]=1;
	for(ri i=2;i<=500000;++i)g[i]=add(g[i-1],mul(g[i-2],i-1));
	for(ri tt=read(),ans;tt;--tt){
		n=read(),m=read(),flag=1,siz=0;
		for(ri i=1;i<=n;++i)e[i].clear(),cnt[i]=dfn[i]=low[i]=vis[i]=0,ban[i].clear();
		for(ri i=1,u,v;i<=m;++i)u=read(),v=read(),e[u].push_back(v),e[v].push_back(u);
		tarjan(1),ans=1;
		if(!flag||siz<n){puts("0");continue;}
		for(ri i=1;i<=n;++i)if(!vis[i])dfs(i,0),ans=mul(ans,f[i]);
		cout<<ans<<'\n';
	}
	return 0;
}

巴特西

2019.02.07 bzoj4784: [Zjoi2017]仙人掌（仙人掌+树形dp）

最新文章

热门文章