Description

P3687 [ZJOI2017]仙人掌 - 洛谷 | 计算机科学教育新生态

Solution

我们先考虑只有一棵树如何处理.

仙人掌可以看做若干环的集合. 特别的, 对于一条没有环的边, 可以加上重边, 那么这个边和它的重边构成一个环.

对于树来说, 问题就可以转化为求加上若干条边, 使树上的每一条边在且仅在一个环内的方案数.

去掉加的边, 也就是说求用若干条边不相交的链将整个树覆盖的方案数.

考虑树形dp.

设 \(f_i\) 表示考虑 \(i\) 的子树与 \(i\) 连向父亲的边, 用若干条边不相交的链覆盖的方案数;

\(g_n\) 表示一个点连出 \(n\) 条边, 用若干条边不相交的链覆盖的方案数, 也就是说, 将 \(n\) 条边两两匹配或者单独留下的方案数.

考虑最后一条边是否匹配, 我们可以得出 \(g_i\) 的通项:

然后求 \(f_i\):

对于非根的点 \(i\), 它连出了 \(|child(i)| + 1\) 条边. 可以考虑将 \(f_j\) 连向父亲的边两两匹配或者单独留下, 根据乘法原理, 有

对于\(i = rt\), 它没有连向父亲的边, 因此

答案即为 \(f_{rt}\).

最后考虑其他的图怎么做:

如果不是仙人掌, 答案为0;

如果图是仙人掌:

对于仙人掌的一个环上的两点 \(p\) 和 \(q\), 显然不能再加边使它们在环外联通. 因此, 我们可以去掉所有的环, 对于剩下的每棵树分别求出答案, 对答案相乘即可.

Code

#include<cstdio>

#include<iostream>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<set>

#include<map>

using namespace std;

#define rep(i,l,r) for(register int i=(l);i<=(r);++i)

#define repdo(i,l,r) for(register int i=(l);i>=(r);--i)

#define il inline

typedef double db;

typedef long long ll;

//---------------------------------------

const int nsz=5e5+50,msz=1e6+50;

const ll nmod=998244353;

int t,n,m;

struct te{int t,pr,del;}edge[msz*2];

int hd[nsz],pe=1;

#define forg(p,i,v) for(int i=hd[p],v=edge[i].t;i;i=edge[i].pr,v=edge[i].t)

void adde(int f,int t){edge[++pe]=(te){t,hd[f],0};hd[f]=pe;}

void adddb(int f,int t){adde(f,t);adde(t,f);}

ll g[nsz];

void init(int bnd){

	g[0]=1,g[1]=1;

	rep(i,2,bnd)g[i]=(g[i-1]+g[i-2]*(i-1))%nmod;

}

int vis[nsz],stkp[nsz],stk[nsz],top=0;

bool solcactus(int p,int e0){

	stk[++top]=e0^1,stkp[p]=top,vis[p]=1;

	forg(p,i,v){

		if(i==e0)continue;

		if(vis[v]){//cir

			if(stkp[v]>stkp[p])continue;

			edge[i].del=edge[i^1].del=1;

			rep(j,stkp[v]+1,stkp[p]){

				if(edge[stk[j]].del)return 0;

				edge[stk[j]].del=edge[stk[j]^1].del=1;

			}

			continue;

		}

		if(solcactus(v,i^1)==0)return 0;

	}

	--top;

	return 1;

}

ll dp[nsz];

void dfs(int p,int fa){

	dp[p]=1,vis[p]=1;

	int cnt=0;

	forg(p,i,v){

		if(v==fa||edge[i].del)continue;

		dfs(v,p);

		dp[p]=dp[p]*dp[v]%nmod;

		++cnt;

	}

	dp[p]=dp[p]*(fa==0?g[cnt]:g[cnt+1])%nmod;

}

ll sol(){

	memset(vis,0,(n+10)*sizeof(int));

	top=0;

	if(solcactus(1,0)==0)return 0;

	memset(vis,0,(n+10)*sizeof(int));

	ll res=1;

	rep(i,1,n){

		if(vis[i]==0)dfs(i,0),res=res*dp[i]%nmod;

	}

	return res;

}

void init1(int n){

	memset(hd,0,(n+10)*sizeof(int));

	pe=1;

}

int main(){

	ios::sync_with_stdio(0),cin.tie(0);

	init(5e5+50);

	cin>>t;

	rep(cs,1,t){

		cin>>n>>m;

		init1(n);

		int a,b;

		rep(i,1,m)cin>>a>>b,adddb(a,b);

		cout<<sol()<<'\n';

	}

	return 0;

}