【ZJOI2017】仙人掌 题解

题目大意

  给出一个无重边无自环的无向连通图（n 个点 m 条边），问有多少种再往上加边的方案，使得新图是仙人掌。
  多组数据， n<=5e5， $\sum m$<=1e6

首先

  先要判断读入的图是否是仙人掌。

一开始的想法

  部分分有树，就先想树怎么做。
  很直观地设 f[i] 表示 i 为根的子树的方案数，g[i] 表示有一条路要往上走的方案数。
  不考虑根的匹配的话，那就是儿子的 f 或 g 乘起来，并且保证 g 有偶数个，再乘上偶数个两两匹配的方案数。
  再考虑根的匹配，相当于枚举一个儿子，然后乘上其他儿子的方案数。

  但是这样做不到线性。因为仙人掌不能含有重边（儿子的根不能和父亲相连），因此在转移的时候，我们总是需要得出一个对所有儿子的值，然后再枚举去掉一个儿子之后的值，而前一个做不到 O(1)，因此后一个也不可能 O(n)。
  这样暴力做是 O(n^2) 的，据说 FFT 可以 log^2？？

对于树

  然后就需要一个转化。
  我们把最后的非环边强行看作两条重边，这样转化之后相当于每个点都必须要有一条延伸出去的边，也就是去掉了不能有重边的限制。（妙啊。。。）
  然后这样的 dp 就比之前的好转移了。f 就是儿子的 g 乘起来，再乘个两两匹配的方案数，g 就是 f 再加上选一个儿子出来然后其他儿子任意的方案数。（不懂请看代码）

  （这时的模型也可以看成是：选若干路径覆盖所有树边，的方案数）

对于无向图

  如果读入的图是个仙人掌，那只要把环边全部断掉就是森林了。因为环边不能参与任何运算，所以去掉是没问题的。
  （妙啊。。。×2）

代码

#include<cstdio>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef long long LL;

const int maxn=5e5+5, maxm=1e6+5;
const LL mo=998244353;

int n,m;

int ReadInt()
{
	char ch=getchar();
	int data=0;
	while (ch<'0' || ch>'9') ch=getchar();
	do{
		data=data*10+ch-'0';
		ch=getchar();
	} while (ch>='0' && ch<='9');
	return data;
}

int tot,fro[2*maxm],go[2*maxm],next[2*maxm],f1[maxn];
bool bt[2*maxm];
void ins(int x,int y)
{
	fro[++tot]=x;
	go[tot]=y;
	bt[tot]=1;
	next[tot]=f1[x];
	f1[x]=tot;
}

int dfn[maxn],low[maxn],sum,z[maxn],z0,rt[maxn];
bool bz[maxn];
bool tarjan(int k,int last)
{
	dfn[k]=low[k]=++sum;
	bz[k]=1;
	z[++z0]=k;
	bool pd=0;
	for(int p=f1[k]; p; p=next[p]) if (go[p]!=last)
	{
		if (!bz[go[p]])
		{
			if (!tarjan(go[p],k)) return 0;
			low[k]=min(low[k],low[go[p]]);
			if (low[go[p]]<dfn[k])
			{
				if (pd) return 0;
				pd=1;
			}
		} else
		{
			low[k]=min(low[k],dfn[go[p]]);
			if (dfn[go[p]]<dfn[k])
			{
				if (pd) return 0;
				pd=1;
			}
		}
	}
	if (dfn[k]==low[k])
	{
		for(; z[z0]!=k; z0--) rt[z[z0]]=k;
		rt[k]=k;
		z0--;
	}
	return 1;
}

LL f[maxn],g[maxn],F[maxn];
void dfs(int k,int last)
{
	rt[k]=0;
	LL sum=1;
	int num=0;
	for(int p=f1[k]; p; p=next[p]) if (bt[p] && go[p]!=last)
	{
		dfs(go[p],k);
		num++;
		sum=sum*g[go[p]]%mo;
	}
	f[k]=F[num]*sum%mo;
	g[k]=(num==0) ?1 :(f[k]+sum*F[num-1]%mo*num)%mo ;
}

int T;
int main()
{
	F[0]=F[1]=1;
	fo(i,2,500000) F[i]=(F[i-1]+F[i-2]*(i-1))%mo;
	
	scanf("%d",&T);
	while (T--)
	{
		n=ReadInt(), m=ReadInt();
		tot=0;
		fo(i,1,n) f1[i]=bz[i]=0;
		fo(i,1,m)
		{
			int x=ReadInt(), y=ReadInt();
			ins(x,y), ins(y,x);
		}
		
		sum=0;
		if (!tarjan(1,0)) {printf("0\n"); continue;}
		fo(p,1,tot) if (rt[fro[p]]==rt[go[p]]) bt[p]=0;
		
		LL ans=1;
		fo(i,1,n) if (rt[i])
		{
			dfs(i,0);
			ans=ans*f[i]%mo;
		}
		
		printf("%lld\n",ans);
	}
}