道理我都懂，但是这个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
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           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]