洛谷P3687 [ZJOI2017]仙人掌 题解

题目链接：P3687 [ZJOI2017]仙人掌

题意：

如果一个无自环无重边无向连通图的任意一条边最多属于一个简单环，我们就称之为仙人掌。所谓简单环即不经过重复的结点的环。

现在九条可怜手上有一张无自环无重边的无向连通图，但是她觉得这张图中的边数太少了，所以她想要在图上连上一些新的边。同时为了方便的存储这张无向图，图中的边数又不能太多。经过权衡，她想要加边后得到的图为一棵仙人掌。

不难发现合法的加边方案有很多，可怜想要知道总共有多少不同的加边方案。

两个加边方案是不同的当且仅当一个方案中存在一条另一个方案中没有的边。

输入格式：

多组数据，第一行输入一个整数 \(Q\) 表示数据组数。

每组数据第一行输入两个整数 \(n,m\) ，表示图中的点数与边数。

接下来 \(m\) 行，每行两个整数 \(u,v(1\le u,v \le n, u\ne v)\) 表示图中的一条边。保证输入的图联通且没有自环与重边。

输出格式：

对于每组数据，输出一个整数表示方案数，当然方案数可能很大，请对 \(998244353\) 取模后输出。

数据范围：

\(1 \le \sum n \le 5\times 10^5,~1 \le m \le \frac{n(n-2)}{2},~\sum m \le 10^6\)

题目就是给了一张无向简单连通图，问你有多少种加边的方法使原图还是个仙人掌。

首先考虑最简单的情况，给定的是一棵树时怎么做。

仙人掌可以看作若干个环的集合。

特别地，对于一条没有环的边，我们可以给它加上一个重边，就成环了。

因此对于树来说，问题就可以转化为求加上若干条边，使树上的每一条边在且仅在一个环上。

注意到加一条边，其实就是在树上选出了一条链，让这个链上的所有点处于同一个环内。

因此我们可以不用管这个加边，进而考虑树上被若干条不相交链覆盖的方案数。

设 \(f_i\) 表示考虑 \(i\) 所在子树与 \(i\) 连向父亲的边，用若干条不相交的链覆盖的方案数。

并设 \(g_i\) 表示一个点连出 \(i\) 条边，用这 \(i\) 条边组成若干条不相交的链的方案数。

考虑最后一条边是否匹配，则 \[ g_i = g_{i-1} + g_{i-2} \times (i-1) \] 后面那个 \(i-1\) 表示的是：前 \(i-1\) 条里面选 \(1\) 条和 \(i\) 配对，即 \(\binom{i-1}{1}\) 。

考虑 \(f_i\) 的转移。首先随便钦定这棵树的根为 \(\mathtt{rt}\) 。

对于非根结点 \(u\) ，它连出去的 \(\mathtt{son}(u) + 1\) 条边。记 \(v \in \mathtt{son}(u)\) 。

可以考虑将所有的 \((u,v)\) 以及 \((u,\mathtt{fa}(u))\) 组成若干条不相交的链，则 \[ f_{u} = g_{\mathtt{son}(u) + 1} \times \prod_{ v \in \mathtt{son}(u)} f_v \] 根节点的话，就是没有父亲而已，所以 \[ f_{\mathtt{rt}} = g_{\mathtt{son}(\mathtt{rt})} \times \prod_{ v \in \mathtt{son}(\mathtt{rt})} f_v \] 最后的答案就是 \(f_{\mathtt{rt}}\) 。

然后考虑其他的情况怎么做。显然原图不是仙人掌的时候一定无解

如果原图是个仙人掌，那我们直接把原来所有的环全部删掉。

删掉之后，原图就有可能变成了森林。森林其实也是一样的，因为每棵树之间的决策相互独立。

注意这题多测，而且 \(\sum n\) 很大，不能直接 memset 。

可以用 memset(head[u], 0, (n+1) * sizeof(int)) ，也可以用时间戳维护。（代码里是后者）

时间复杂度 \(\mathcal{O}(\sum n + \sum m)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 998244353;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
    template<typename T>void print(T k) { write(k); pc('\n'); }
}using namespace FastIO;
#define N ((int)(5e5+15))
#define M ((int)(1e6+15))

int n,m,pos=1,top,f[N],g[N],stk[N],dfn[N],head[N],vis[N];
struct Edge { int u,v,next,del; } e[M * 2];
void addEdge(int u,int v)
{ e[++pos] = {u,v,head[u],0}; head[u] = pos; }
void init(int n)
{
    g[0] = 1; g[1] = 1;
    for(int i=2; i<=n; i++) g[i] = (g[i-1] + g[i-2] * (i-1)) % mod;
}
int tim = 0;
// 这里不用fa是为了方便下面的删边
bool check(int u,int e0)
{
    stk[++top] = e0 ^ 1; dfn[u] = top; vis[u] = tim;
    for(int i=head[u]; i; i=e[i].next)
    {
        int v = e[i].v;
        if(i == e0) continue;
        if(vis[v] == tim)
        {
            if(dfn[v] > dfn[u]) continue;
            e[i].del = e[i^1].del = 1;
            for(int j = dfn[v]+1; j<=dfn[u]; j++)
            {
                if(e[stk[j]].del) return 0; // 一条边在多个环内，不合法
                e[stk[j]].del = e[stk[j] ^ 1].del = 1;
            }
            continue;
        }
        if(!check(v, i^1)) return 0;
    }
    --top; return 1;
}
void dfs(int u,int fa)
{
    f[u] = 1; vis[u] = tim;
    int cnt = 0;
    for(int i=head[u]; i; i=e[i].next)
    {
        int v = e[i].v; if(v == fa || e[i].del) continue;
        dfs(v,u); f[u] = f[u] * f[v] % mod; ++cnt;
    }
    f[u] = f[u] * (fa==0 ? g[cnt] : g[cnt+1]) % mod; 
}
int solve()
{
    top = 0; ++tim;
    if(!check(1,0)) return 0;
    int res = 1; ++tim;
    for(int i=1; i<=n; i++)
        if(vis[i] < tim) { dfs(i,0); res = res * f[i] % mod; }
    return res;
}
void clear()
{ for(int i=0; i<=n; i++) head[i] = 0; pos = 1; }
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    init(N-5); int Q,a,b;
    for(read(Q); Q--; clear())
    {
        read(n); read(m);
        for(int i=1,u,v; i<=m; i++)
        {
            read(u); read(v);
            addEdge(u,v); addEdge(v,u);
        }
        print(solve());
    }
    return 0;
}