[ZJOI2017] 仙人掌

Description

如果一个无自环无重边无向连通图的任意一条边最多属于一个简单环，我们就称之为仙人掌。所谓简单环即不经过重复的结点的环。现在给定一张无自环无重边的无向连通图，求有多少种合法的加边方案，使得加边后原图是张仙人掌图。$T$ 组测试数据。

$\sum n\leq 5\times 10^5,\sum m\leq 10^6$

Solution

如果原图不是仙人掌，则无解。
如果原图是仙人掌，原图一定被环分成了若干棵树。环上一定不能加边，我们只需要考虑树上的情况。
在树上加边使得每条边至多属于一个环相当于是在树上选出若干条不相交的链，树上的每条边只能被一条或零条链覆盖。我们统一一下，如果是零条链，我们视作其加了一条重边。于是问题变成了选出若干条不相交的链，覆盖到树上的每一条边。易证明两个问题等价，因为我们只需要将长度为 $1$ 的链视作没加即可。
对于点 $u$ ，假设其度数为 $\text{deg}_u$ ，那么这 $\text{deg}_u$ 条边的每条边既可以选择不匹配，也可以选择匹配一个。可以发现匹配与否的方案数与树的形态无关，我们单独拿出来计算。
设 $g_i$ 表示将 $i$ 条边配对/不配对的方案数。那么有

$g_i=g_{i-1} + g_{i-2}\times (i-1)$

这个式子可以通过分类讨论第 $i$ 条边是否配对得到。
设 $f_u$ 表示子树 $u$ 加边加成一个仙人掌的方案数，那么有

$f_u =g_{\text{deg}_u}\times \prod_{u\rightarrow v} f_v$

答案自然就是若干个树的根的 $f$ 之积。复杂度 $\mathcal{O}(n+m)$ 。

第一步的转化比较简单，第二步的 DP 是一个小 trick 。以后做到树/图上链覆盖的模型时要能看出来。

Code

const int N = 5e5 + 5, M = 1e6 + 6, mod = 998244353;
using namespace std;
int n, m, top, num;
int vis[N], dfn[N], ins[N], stk[M];
int head[N], nt[M << 1], to[M << 1], del[M << 1];
int f[N], g[N];
bool tar(int p, int d){
    dfn[p] = ++top, ins[p] = top, stk[top] = d;
    for(int i = head[p]; i; i = nt[i])if(i ^ d){
        int v = to[i];
        if(dfn[v]){
            if(ins[p] < ins[v]) continue;
            del[i] = del[i ^ 1] = true;
            for(int j = ins[v] + 1; j <= ins[p]; ++j){
                int id = stk[j];
                if(del[id] == true) return false;
                del[id] = del[id ^ 1] = true;
            }

        }
        else if(tar(v, i ^ 1) == 0) return false;
    }
    return --top, true;
}

void dfs(int p, int fa){
    f[p] = 1, vis[p] = 1;
    int cnt = 0;
    for(int i = head[p]; i; i = nt[i]){
        if(to[i] == fa || del[i]) continue;
        ++cnt; dfs(to[i], p);
        f[p] = 1ll * f[p] * f[to[i]] % mod;
    }
    f[p] = 1ll * f[p] * (fa == 0 ? g[cnt] : g[cnt + 1]) % mod;
}
void Add(int x, int y){
    ++num; nt[num] = head[x]; head[x] = num; to[num] = y; del[num] = 0;
    ++num; nt[num] = head[y]; head[y] = num; to[num] = x; del[num] = 0;
}
void solve(){
    
    r(n, m);
    top = 0, num = 1;
    for(int i = 1; i <= n; ++i)
        vis[i] = dfn[i] = ins[i] = head[i] = 0;
    
    for(int i = 1, x, y; i <= m; ++i)
        r(x, y), Add(x, y);
    if(tar(1, 0) == 0) return puts("0"), void();
    long long ans = 1;
    for(int i = 1; i <= n; ++i)
        if(!vis[i]) 
            dfs(i, 0), ans = ans * f[i] % mod;
    w(ans);
}
int main(){

    int T;r(T);
    g[0] = g[1] = 1;
    for(int i = 2; i < N; ++i)
        g[i] = (g[i - 1] + 1ll * g[i - 2] * (i - 1) % mod) % mod;
    while(T--)
        solve();
    return 0;
}