题解 P3687 【[ZJOI2017]仙人掌】

2020-04-28 17:11:38



[ZJOI2017]仙人掌


题意:

给定一张无向连通图,问你有多少种填边方式,使填完边之后的图是一颗仙人掌。

仙人掌定义: 无自环无重边无向连通图的任意一条边最多属于一个简单环,我们就称之为仙人掌。

点数 5*1e5 边数 1e6

方案数 对 998244353 取模


题解:

如果原图已经不满足仙人掌的性质 直接输出0即可。

我们先考虑原图是树的情况

对于一个树

我们把加上一条边认为是将树上的简单路径覆盖一次

如果一条树边没有被覆盖,我们可以认为是这个树边被单独覆盖了

所以我们的问题可以转化为,用若干条不相交的链覆盖这棵树的方案数

(是不是有点熟悉.........和GMOJ内道差不多....只是这个没有强制K条,少一维状态罢了....)

那么方法类似, gn 表示一个点连出 n 条边, 用若干条边不相交的链覆盖的方案数,

也就是说, 将 n 条边两两匹配或者单独留下的方案数. $$ g[i]=g[i-1]+(i-1)*g[i-2] $$ fn 表示 对于这颗子树要求的答案 $$ if(x==root) f[x]=\prod_{y=son(x)}f[y] * g[deg[i]] $$

$$ else \qquad f[x]=\prod_{y=son(x)} f[y] * g[deg[i]+1] $$

答案即为f root

考虑如果是一颗仙人掌,我们可以完全不考虑环上的边

因为不可能链接 跨越环上的边 否则一定不满足最后是一颗仙人掌的性质

所以我们考虑所有不包含环上边的极大连通块(森林........)

最后把这些答案累乘起来即可


代码:

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int maxn=5e5+5,mod=998244353;

inline int read(){
    int x=0,f=1;
    char p=getchar();
    while(!isdigit(p)){
        if(p=='-') f=-1;
        p=getchar();
    }
    while(isdigit(p)) x=(x<<3)+(x<<1)+(p^48),p=getchar();
    return x*f;
}

int dp[maxn],f[maxn],t,n,m,head[maxn],ver[maxn<<2],fa[maxn],ans;
int nxt[maxn<<2],cnt,dfn[maxn],num[maxn],st[maxn<<2],dep[maxn],tim;
struct node{
    int x,d;
}a[maxn];

inline bool cmp(node a,node b){
    return a.d<b.d;
}

inline void add(int x,int y){
    nxt[++cnt]=head[x];
    st[cnt]=x;
    head[x]=cnt;
    ver[cnt]=y;
}

inline void dfs(int x){
    dfn[x]=++tim;
    for(int i=head[x];i;i=nxt[i]){
        int y=ver[i];
        if(dfn[y]) continue;
        fa[y]=x;dep[y]=dep[x]+1;
        dfs(y);
    }
}

inline void work(int x,int rt){
    f[x]=1;int tot=0;num[x]=-1;
    for(int i=head[x];i;i=nxt[i]){
        int y=ver[i];
        if(num[y]!=1) continue;
        tot++;work(y,rt);f[x]=f[x]*f[y]%mod;
    }
    if(x==rt) f[x]=f[x]*dp[tot]%mod;
    else f[x]=f[x]*dp[tot+1]%mod;
}

inline void solve(){
    ans=1;n=read();m=read();for(int i=1;i<=n;i++) head[i]=0,dfn[i]=0,num[i]=0;cnt=1;tim=0;
    for(int i=1,x,y;i<=m;i++) x=read(),y=read(),add(x,y),add(y,x);
    dfs(1);
    for(int i=2;i<=cnt;i+=2){
        int x=st[i],y=ver[i];
        if(dfn[x]<dfn[y]) swap(x,y);
        while(x!=y){
            if(num[x]==2){
                cout<<0<<endl;
                return;
            }
            num[x]++;x=fa[x];
        }
    }
    for(int i=1;i<=n;i++) a[i].d=dep[i],a[i].x=i;
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++){
        int x=a[i].x;
        if(num[x]==-1) continue;
        work(x,x);ans=ans*f[x]%mod;
    }
    cout<<ans<<endl;
}

signed main(){
    dp[1]=1;dp[0]=1;
    for(int i=1;i<=500000;i++) dp[i]=(dp[i-1]+dp[i-2]*(i-1))%mod;
    t=read();
    while(t--){
        solve();
    }
    return 0;
}