LibreOJ 2250 「ZJOI2017」仙人掌

注意到若给出的图非仙人掌，则一定无解。
否则，考虑把环拆掉，剩下一片森林。答案即森林中每棵树分别加边成为仙人掌的方案数。

对于一棵树，在其上加边使其变为仙人掌的方案数等价于用若干条不相交的链覆盖这棵树的方案数。
考虑 DP，设 fu 表示 u 子树内的边和 u 到其父亲的边被若干条链覆盖的方案数。
易得转移 fu=coedeg(u)∏(u,v)∈Efv，其中将树看做外向树。

注意到系数 coedeg(u) 相当于把和 u 相连的所有边接成链或单独成链的方案数。
易得 DP coei=coei−1+(i−1)coei−2。

代码：

#include <cstdio>
#include <cstring>
using namespace std;
const int N = 5e5;
const int M = 1e6;
const int mod = 998244353;
int T,n,m;
int to[(M << 1) + 5],pre[(M << 1) + 5],first[N + 5],edge_tot;
int del[(M << 1) + 5];
inline void add(int u,int v)
{
    int &tot = edge_tot;
    to[tot] = v,del[tot] = 0,pre[tot] = first[u],first[u] = tot++;
}
int vis[N + 5],fa[N + 5],dep[N + 5],las[N + 5];
int s[N + 5],top;
int check(int p)
{
    s[++top] = p,vis[p] = 1;
    for(register int i = first[p];~i;i = pre[i])
        if(i ^ las[p])
            if(vis[to[i]])
            {
                if(dep[p] > dep[to[i]])
                {
                    del[i] = del[i ^ 1] = 1;
                    for(register int j = dep[to[i]] + 1;j <= dep[p];++j)
                    {
                        if(del[las[s[j]]])
                            return 0;
                        del[las[s[j]]] = del[las[s[j]] ^ 1] = 1;
                    }
                }
            }
            else
            {
                las[to[i]] = i ^ 1,dep[to[i]] = dep[p] + 1;
                if(!check(to[i]))
                    return 0;
            }
    --top;
    return 1;
}
int f[N + 5],coe[N + 5],ans;
void dfs(int p)
{
    int cnt = (bool)fa[p];
    f[p] = 1;
    for(register int i = first[p];~i;i = pre[i])
        if((to[i] ^ fa[p]) && !del[i])
            fa[to[i]] = p,dfs(to[i]),f[p] = (long long)f[p] * f[to[i]] % mod,++cnt;
    f[p] = (long long)f[p] * coe[cnt] % mod;
}
int main()
{
    coe[0] = coe[1] = 1;
    for(register int i = 2;i <= N;++i)
        coe[i] = (coe[i - 1] + (long long)coe[i - 2] * (i - 1)) % mod;
    scanf("%d",&T);
    for(;T;--T)
    {
        scanf("%d%d",&n,&m),memset(first + 1,-1,sizeof(int) * n),edge_tot = 0,ans = 1;
        int u,v;
        for(register int i = 1;i <= m;++i)
            scanf("%d%d",&u,&v),add(u,v),add(v,u);
        memset(vis + 1,0,sizeof(int) * n),memset(dep + 1,0,sizeof(int) * n),top = 0,las[1] = -1,dep[1] = 1;
        if(!check(1))
        {
            puts("0");
            continue;
        }
        memset(fa + 1,0,sizeof(int) * n);
        for(register int i = 1;i <= n;++i)
            if(!fa[i])
                dfs(i),ans = (long long)ans * f[i] % mod;
        printf("%d\n",ans);
    }
}