「ZJOI2017」仙人掌 - 神奇转化+树形动规

题目大意

    如果一个无自环无重边无向连通图的任意一条边最多属于一个简单环，我们就称之为仙人掌。所谓简单环即不经过重复的结点的环。

    现在九条可怜手上有一张无自环无重边的无向连通图，但是她觉得这张图中的边数太少了，

    所以她想要在图上连上一些新的边。同时为了方便的存储这张无向图，图中的边数又不能太多。

    经过权衡，她想要加边后得到的图为一棵仙人掌。不难发现合法的加边方案有很多，可怜想要知道总共有多少不同的加边方案。两个加边方案是不同的当且仅当一个方案中存在一条另一个方案中没有的边。

---

题目分析

神题一道。
麻麻，题目中又有$998244353$条可怜。

首先，将加边问题转化为覆盖问题，加一条非树边相当于在原图中覆盖掉原有的树边，要求一条边最多被覆盖一次。
然后，不难发现仙人掌是假的，我们可以去掉原图的环边，因为环边一定不能被覆盖。
去掉环了过后，原图变为了一个森林，而树与树之间是不能连边的，故每棵树的答案独立，可以乘起来。

但现在题目依然不好做，因为一条边最多被覆盖一次这个条件不好计数。
这个时候就需要玄学了，你看，题目说了无自环无重边无向连通图，无自环无重边，无重边！
故一个二元环不会被计算为答案。
那么对于没有被覆盖的边，不妨添加一条重边将其变成二元环，这样转化前后完全等价。
故现在的问题转化为：每条边恰好被覆盖一次。

然后就可以进行动规了。
我们从下往上一层一层地考虑树形动规。
设$f(i)$表示$i$结点的子树连边情况已经统计，$i$到$i$的父亲连边情况也已经统计的方案数。
若当前层的儿子均已递归处理完毕，那么儿子们均有一条向上连向父亲的边，现在需要考虑将这些连上来的边合并起来。

如图，相同形状的边表示连在一起，注意，儿子可以和通往父亲的边连在一起。
这样相当于把儿子和父亲拿出来做了个两两匹配，有的点也可以不匹配（某些没有匹配的边可以视作重边二元环）。

这样，匹配的方案数可以使用递推解决，设$g(i)$表示$i$个点的匹配方案数：

$$g(n)=g(n-1)+(n-1)g(n-2)$$

然后$f()$数组就很好动规了。
先把儿子的全部乘起来，再乘自己的$g$即可。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>

using namespace std;

typedef long long LL;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(!isdigit(x)) {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(isdigit(x)) {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=500005,mod=998244353;

int n,m,step=0,Dfn[maxn],Lowlink[maxn],Stack[maxn],Belong[maxn],BCC=0,top=0;
LL f[maxn],g[maxn];
bool bj=1,vst[maxn];
vector<int> edges[maxn],edges2[maxn];

void Tarjan(int Now,int fa) {
	Dfn[Now]=Lowlink[Now]=++step;
	Stack[++top]=Now;
	bool flag=0;
	for(int Next:edges[Now]) {
		if(Next==fa)continue;
		if(!Dfn[Next]) {
			Tarjan(Next,Now);
			Lowlink[Now]=min(Lowlink[Now],Lowlink[Next]);
			if(Lowlink[Next]<Dfn[Now]) {
				if(flag) {bj=0;return;}
				flag=1;
			}
		} else {
			Lowlink[Now]=min(Lowlink[Now],Dfn[Next]);
			if(Dfn[Next]<Dfn[Now]) {
				if(flag) {bj=0;return;}
				flag=1;
			}
		}
	}
	if(Dfn[Now]==Lowlink[Now]) {
		BCC++;
		int y;
		do {
			y=Stack[top--];
			Belong[y]=BCC;
		} while(y!=Now);
	}
}

void TreeDp(int Now,int fa) {
	f[Now]=vst[Now]=1;
	for(int Next:edges2[Now]) {
		if(Next==fa)continue;
		TreeDp(Next,Now);
		f[Now]=f[Now]*f[Next]%mod;
	}
	f[Now]=f[Now]*g[edges2[Now].size()]%mod;
}

void Clear() {
	for(int i=1; i<=n; i++) {
		Dfn[i]=vst[i]=0;
		edges[i].clear();
		edges2[i].clear();
	}
	bj=1;
	BCC=0;
}

void AddEdge(int x,int y) {edges[x].push_back(y);}
void AddEdge2(int x,int y) {edges2[x].push_back(y);}

int main() {
	g[0]=g[1]=1;
	for(int i=2; i<=500000; i++)g[i]=(g[i-1]+g[i-2]*(i-1)%mod)%mod;
	int t=Get_Int();
	while(t--) {
		Clear();
		n=Get_Int();
		m=Get_Int();
		for(int i=1; i<=m; i++) {
			int x=Get_Int(),y=Get_Int();
			AddEdge(x,y);
			AddEdge(y,x);
		}
		for(int i=1; i<=n; i++)if(!Dfn[i])Tarjan(i,0);
		if(!bj) {
			puts("0");
			continue;
		}
		for(int Now=1; Now<=n; Now++)
			for(int Next:edges[Now])
				if(Belong[Now]!=Belong[Next])AddEdge2(Now,Next);
		LL ans=1;
		for(int i=1; i<=n; i++)if(!vst[i])TreeDp(i,0),ans=ans*f[i]%mod;
		printf("%lld\n",ans);
	}
	return 0;
}