题解 P3687 【[ZJOI2017]仙人掌】
whyl
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*
考虑如果是一颗仙人掌，我们可以完全不考虑环上的边
因为不可能链接 跨越环上的边 否则一定不满足最后是一颗仙人掌的性质
所以我们考虑所有不包含环上边的极大连通块（森林........）
最后把这些答案累乘起来即可
***
代码：
```c++
#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;
}
```