题解 P6790 【[SNOI2020] 生成树】

Karry5307 · 2021-02-03 10:27:31 · 题解

题意

给定一个 n 个点 m 条边的图，保证这个图删掉一条边之后是边仙人掌，求该图生成树个数。

\texttt{Data Range:}1\leq n,m\leq 5\times 10^5

题解

广义串并联图。

注意到原图是广义串并联图，所以可以考虑对每条边进行 DP，然后在收缩的时候进行转移。

一个思路是设 f_e 表示 e 这条边在生成树上的方案，g_e 表示这条边不在生成树上的方案，那么对于收缩的三种操作有：

删 1 度点：直接将 f_e 乘进答案即可。
缩 2 度点：这两条边不可能同时不存在于生成树上，同时缩出来的边只有当两条边都存在时才存在，于是有如下转移：

\begin{cases}f_e=f_{e_1}f_{e_2}\\g_e=f_{e_1}g_{e_2}+f_{e_2}g_{e_1}\end{cases}

叠合重边：这两条边不可能同时存在于生成树上，同时缩出来的边只有当两条边都不存在时才不存在，于是有如下转移：

\begin{cases}f_e=f_{e_1}g_{e_2}+f_{e_2}g_{e_1}\\g_e=g_{e_1}g_{e_2}\end{cases}

然后拓扑排序构造出整个收缩序列即可，删边的话可以使用哈希表或者是 map，实测 map 比各种哈希表优秀，实现上有亿点细节要注意。

代码

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef long long int li;
const ll MAXN=5e5+51,MOD=998244353;
queue<ll>q;
ll n,m,u,v,totd,top,x,y,r,res=1;
ll f[MAXN],g[MAXN],deg[MAXN];
map<ll,ll>mp[MAXN];
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
}
int main()
{
    n=read(),m=read(),g[0]=1;
    for(register int i=1;i<=m;i++)
    {
        u=read(),v=read();
        !mp[u][v]?g[mp[u][v]=mp[v][u]=++totd]=1,deg[u]++,deg[v]++:1;
        f[mp[u][v]]++;
    }
    for(register int i=1;i<=n;i++)
    {
        deg[i]<=2?q.push(i):(void)1;
    }
    while(!q.empty())
    {
        top=q.front(),q.pop();
        if(!deg[top])
        {
            continue;
        }
        if(deg[top]==1)
        {
            tie(u,x)=*mp[top].begin(),deg[top]=0,res=(li)res*f[x]%MOD;
            mp[top].clear(),mp[u].erase(top),--deg[u]<=2?q.push(u):(void)1;
        }
        if(deg[top]==2)
        {
            tie(u,x)=*mp[top].begin(),tie(v,y)=*next(mp[top].begin()),r=mp[u][v];
            mp[top].clear(),mp[u].erase(top),mp[v].erase(top),deg[top]=0;
            g[x]=((li)g[x]*f[y]+(li)f[x]*g[y])%MOD,f[x]=(li)f[x]*f[y]%MOD;
            f[x]=((li)f[x]*g[r]+(li)g[x]*f[r])%MOD,g[x]=(li)g[x]*g[r]%MOD;
            mp[u][v]=mp[v][u]=x;
            r?--deg[u]<=2?q.push(u):(void)1,--deg[v]<=2?q.push(v):(void)1:(void)1;
        }
    }
    printf("%d\n",res);
}