这图可以说是非常形象了2333

模拟赛的时候打了个表发现为一条链的时候答案是\(2^{n-2}\)竟然顺便过了第一个点

然后之后订正的时候强联通分量打错了调了一个上午

首先不难发现我们可以去掉所有在环上的边，那么就变成了一个森林，不同的树之间不可能有连边，那么只要所有树的答案乘起来就好了，只要在每一棵树内部树形\(dp\)即可

考虑对于\(u\)，它的子树如何统计答案

我们强制子树必须得向外连一条边（显然最多只有一条），然后往上统计

如果子树里没有向外连边，每一棵子树的答案乘起来

如果向外连边的话，那么要把子树内的边两两匹配上。设\(g_i\)为\(i\)个点互相两两匹配的方案数，那么递推式为\[g_i=g_{i-1}+(i-1)\times g_{i-2}\]

边界条件为\(g_0=g_1=1\)

上面的意思是，如果第\(i\)个不连边，那么方案数就是\(g_{i-1}\)，如果连边，那么有\(i-1\)种连法，连完后这两个点都不能再连边了

那么要把子树内的边两两匹配，如果当前节点是根，那么就是子树内向外连的每条链互相匹配，记\(tot\)为当前节点儿子个数，那么就是\(g_{tot}\)，否则链还可以继续往上连，那么是\(g_{tot+1}\)，可以考虑为把当前节点也加入匹配的队列，如果有链和它连上就代表这条链要继续向外连

然后记得开始的时候判一下是不是仙人掌就好了

//minamoto#include
    
     #define R register#define fp(i,a,b) for(R int i=a,I=b+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)template
      
       inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}inline void swap(R int &x,R int &y){x^=y^=x^=y;}using namespace std;char buf[1<<21],*p1=buf,*p2=buf;inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}int read(){    R int res,f=1;R char ch;    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}void write(int x){if(x>9)write(x/10);putchar(x%10+48);}void writeln(R int x){write(x);putchar('\n');}const int N=1e6+5,P=998244353;inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}int ksm(R int x,R int y){    R int res=1;    for(;y;y>>=1,x=mul(x,x))if(y&1)res=mul(res,x);    return res;}struct eg{int v,nx,w;}e[N<<1];int head[N],tot=1;inline void add_edge(R int u,R int v){e[++tot]={v,head[u]},head[u]=tot;}int dfn[N],col[N],vis[N],f[N],g[N],st[N],low[N];int n,m,cnt,top,tim,u,v,ans;bool qwq;inline void clr(){fp(i,1,n)dfn[i]=col[i]=f[i]=vis[i]=head[i]=0;tim=cnt=top=qwq=0,tot=ans=1;}void tarjan(int u,int fa){    bool flag=0;st[++top]=u;    dfn[u]=low[u]=++tim;    go(u)if(v!=fa){        if(!dfn[v]){            tarjan(v,u);cmin(low[u],low[v]);            if(low[v]