链接

LOJ2250
Luogu3687

题解

• 先把环全都扔掉（字面意思），因为你不可能再在环上加边。但是在这个过程中你要科学判断读入的是否是圆方树。（这个东西我调了半天）
• 然后就是树上问题。
• 转化成这样：每次选不相邻的两个点，将这两点间的简单路径上的每条边覆盖上。求每条边最多被覆盖一次的方案数。
• 记\(f_{i,0}\)表示\(i\)号点子树内部全都消化完了的方案数，\(f_{i,1}\)表示\(i\)号点子树中还能有一个不是从\(i\)出发的向上路径的方案数。再记\(i\)有\(ch(i)\)个孩子。
• 我们发现可以转换成一个序列问题。每个点选了有一个权值，不选有一个权值，你可以将所有选了的点任意两两配对，一个方案的权值就是他所有点的权值的积。\(f_{i,0}\)就是所有方案的权值之和。
• 点\(j\)选了的权值是什么？\(f_{j,0}+f_{j,1}\)；不选的权值是什么？\(f_{j,0}+f_{j,1}\)。他们竟然一样！（我写的时候在这里卡了半天，因为我压根没有去想他们的权值会一样）。
• 我们只用算有多少种选择及配对方案。记\(g_i\)表示\(i\)个点的选择方案，显然有\(g_{i}=g_{i-1}+(i-1)g_{i-2},g_0=g_1=1\)。（我又在这里卡了半天，因为我一上来就莽式子，发现那是一大坨组合数）
• 好，\(f_{i,0}\)算完了。\(f_{i,0}=h_{ch(i)}\prod (f_{j,0}+f_{j,1})\)
• 至于\(f_{i,1}\)，我们发现我们只要从他的孩子中选择一个点\(j\)，让他一枝独秀，可以往上走就行了。我们惊奇地发现\(j\)内部可以被选择往上走的方案数依旧是\(f_{j,0}+f_{j,1}\)。
• 那，\(f_{i,1}\)也算完了。\(f_{i,1}=h_{ch(i)-1}ch(i)\prod (f_{j,0}+f_{j,1})\)。
• 你过题了，你拿到了浙江省选的100分，并最终获得了标准分进队的殊荣。让我们恭喜你。

代码

#include<bits/stdc++.h>
#define LL long long
#define MAXN 1000000
#define MAXM 1000000
#define MOD 998244353
using namespace std;
template<typename T>void Read(T &cn)
{
	char c;int sig = 1;
	while(!isdigit(c = getchar()))if(c == '-')sig = -1; cn = c-48;
	while(isdigit(c = getchar()))cn = cn*10+c-48; cn*=sig;
}
template<typename T>void Write(T cn)
{
	if(cn < 0) {putchar('-'); cn = 0-cn; }
	int wei = 0; T cm = 0; int cx = cn%10; cn/=10;
	while(cn)cm = cm*10+cn%10,cn/=10,wei++;
	while(wei--)putchar(cm%10+48),cm/=10;
	putchar(cx+48);
}
template<typename T>void Min(T &cn, T cm) {cn = cn < cm ? cn : cm; }
struct Tree{
	struct qwe{
		int a,b,ne;
		void mk(int cn, int cm, int cx) {a = cn; b = cm; ne = cx; }
	};
	qwe a[MAXM+1];
	int alen;
	int head[MAXN+1];
	void build(int cn) {alen = 0; for(int i = 1;i<=cn;i++) head[i] = 0; }
	void lian(int cn, int cm) {a[++alen].mk(cn,cm,head[cn]); head[cn] = alen; }
	void lian_d(int cn, int cm) {lian(cn, cm); lian(cm, cn); }
}T1, T2;
int n,m,t;
int dfn[MAXN+1], low[MAXN+1], zhan[MAXN+1], guo[MAXN+1], shi, zlen;
int vis[MAXN+1];
LL f[MAXN+1][2];
LL h[MAXN+1];
void yuchu(int cn) {h[0] = h[1] = 1; for(int i = 2;i<=cn;i++) h[i] = (h[i-1]+1ll*(i-1)*h[i-2])%MOD; }
int tarjan(int cn, int fa)
{
	guo[cn] = 0;
	dfn[cn] = low[cn] = ++shi;
	zhan[++zlen] = cn;
	for(int i = T1.head[cn];i;i = T1.a[i].ne)
	{
		int y = T1.a[i].b;
		if(y == fa) continue;
		if(dfn[y]) {
			Min(low[cn], dfn[y]);
			if(guo[cn] && guo[y] != cn) return -1;
			if(guo[y] != cn) guo[cn] = y;
		}
		else {
			int lin = zlen;
			int lin2 = tarjan(y, cn);
			Min(low[cn], low[y]);
			if(lin2 == -1) return -1;
			if(low[y] >= dfn[cn]) {
				if(lin2 != cn && lin2 != 0) return -1;
				if(zlen == lin+1) T2.lian_d(cn, zhan[zlen]);
				zlen = lin;
			}
			else {
				if(lin2 && guo[cn]) return -1;
				if(!guo[cn]) guo[cn] = lin2;
			}
		}
	}
	return guo[cn];
}
void dfs(int cn, int fa)
{
	vis[cn] = 1; 
	f[cn][0] = 1;
	int ge = 0;
	for(int i = T2.head[cn];i;i = T2.a[i].ne) 
	{
		int y = T2.a[i].b;
		if(y == fa) continue;
		dfs(y, cn);
		f[cn][0] = 1ll*f[cn][0]*(f[y][1] + f[y][0])%MOD;
		ge++;
	}
	f[cn][1] = f[cn][0] * h[ge-1]%MOD *ge%MOD;
	f[cn][0] = f[cn][0] * h[ge]%MOD;
}
void zuo()
{
	Read(n); Read(m);
	T1.build(n); T2.build(n);
	for(int i = 1;i<=m;i++) {int bx,by; Read(bx); Read(by); T1.lian_d(bx,by); }
	shi = zlen = 0; for(int i = 1;i<=n;i++) dfn[i] = low[i] = 0;
	if(tarjan(1, 0) == -1) {puts("0"); return; }
	LL ans = 1; for(int i = 1;i<=n;i++) vis[i] = 0;
	for(int i = 1;i<=n;i++) if(!vis[i]) dfs(i, 0), ans = ans*f[i][0]%MOD;
	Write(ans); puts("");
}
int main() {yuchu(MAXN); Read(t); while(t--) zuo(); return 0; }