道理我都懂，但是这个DP难度真的很大
先tarjan一下判断是不是仙人掌
对于环上的点，它们是不能相连的，直接拆了完事
然后我们成功的把仙人掌转成了树，就是一个treeDP
问题转化成在一棵树上，可以选择两个点将其树上路径覆盖，求不相交的覆盖方案数
令f[x]表示x子树中的方案数，它没有一条单向向上的路径，g[x]表示有的方案数，这个比较容易想到
但是如果让子节点的g两两匹配更新f[x]，这样是极为复杂的，因为两两匹配数量是不定的
我们没有办法快速统计在两两匹配数量不同的情况下的方案数。
这是我遇到的瓶颈，%了网上的题解才知道以下做法：
令h[i]表示有i个孩子匹配，可以不匹配的方案数
f[x]=∏g[son]*h[子节点数]
选择不匹配，相当于由这个孩子连向了这个根节点，如果是重边，理解为不连，相当于舍弃了这条向上的边
这样就涵盖住所有的情况了：路径合并、某些子树不向上连（不必要把所有的边覆盖）
通过不连，把匹配数量不定的情况合并了，换个理解，舍弃的边视为连了自环，把所有的边都覆盖了，而这个等价于舍弃
同理g[x]=f[x]+∏g[son]*h[子节点数-1]*子节点数
意思是首先x可以选择自己向上连，也可以选择一个孩子向上，方案为g[y]，其他的就是∏（不包括y）g[son]*h[子节点数-1]，有子节点数种选择
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; typedef long long LL; const LL mod=998244353; int read() { int x=0,f=1;char ch=getchar(); while('0'>ch||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } struct node { int x,y,next;bool bk; }a[2100000];int len,last[510000]; void ins(int x,int y) { len++; a[len].x=x;a[len].y=y;a[len].bk=true; a[len].next=last[x];last[x]=len; } int z,dfn[510000],fr[510000];bool bk; void dfs(int x) { if(bk==true)return ; dfn[x]=++z; for(int k=last[x];k;k=a[k].next) if(dfn[a[k].y]==0)fr[a[k].y]=k,dfs(a[k].y); for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(a[fr[y]].x!=x&&dfn[x]<dfn[y]) { if(a[k].bk==false||a[k^1].bk==false){bk=true;return ;} a[k].bk=a[k^1].bk=false; int p=fr[y]; while(y!=x) { if(a[p].bk==false||a[p^1].bk==false){bk=true;return ;} a[p].bk=a[p^1].bk=false; y=a[p].x;p=fr[y]; } } } } bool v[510000]; LL f[510000],g[510000],h[510000]; void treedp(int x,int fa) { v[x]=true; f[x]=1,g[x]=0; int s=0; for(int k=last[x];k;k=a[k].next) { if(!a[k].bk)continue; int y=a[k].y; if(v[y]==false) { treedp(y,x); f[x]=(f[x]*g[y])%mod; s++; } } g[x]=(f[x]*h[s]%mod+f[x]*h[s-1]%mod*s%mod)%mod; f[x]=f[x]*h[s]%mod; } int main() { freopen("a.in","r",stdin); freopen("a.out","w",stdout); h[0]=1;h[1]=1;for(int i=1;i<=500000;i++)h[i]=(h[i-1]+((i-1)*h[i-2])%mod)%mod; int T=read(),n,m,x,y; while(T--) { n=read(),m=read(); len=1;for(int i=1;i<=n;i++)last[i]=dfn[i]=0,v[i]=false; for(int i=1;i<=m;i++) { x=read(),y=read(); ins(x,y),ins(y,x); } z=0;bk=false; fr[1]=0;dfs(1); if(bk==true){printf("0 ");continue;} LL ans=1; for(int i=1;i<=n;i++) if(v[i]==false) { treedp(i,0); ans=(ans*f[i])%mod; } printf("%lld ",ans); } return 0; }