Description
P3687 [ZJOI2017]仙人掌 - 洛谷 | 计算机科学教育新生态
Solution
我们先考虑只有一棵树如何处理.
仙人掌可以看做若干环的集合. 特别的, 对于一条没有环的边, 可以加上重边, 那么这个边和它的重边构成一个环.
对于树来说, 问题就可以转化为求加上若干条边, 使树上的每一条边在且仅在一个环内的方案数.
去掉加的边, 也就是说求用若干条边不相交的链将整个树覆盖的方案数.
考虑树形dp.
设 (f_i) 表示考虑 (i) 的子树与 (i) 连向父亲的边, 用若干条边不相交的链覆盖的方案数;
(g_n) 表示一个点连出 (n) 条边, 用若干条边不相交的链覆盖的方案数, 也就是说, 将 (n) 条边两两匹配或者单独留下的方案数.
考虑最后一条边是否匹配, 我们可以得出 (g_i) 的通项:
[g_i = g_{i-1} + g_{i-2} cdot (i-1)
]
然后求 (f_i):
对于非根的点 (i), 它连出了 (|child(i)| + 1) 条边. 可以考虑将 (f_j) 连向父亲的边两两匹配或者单独留下, 根据乘法原理, 有
[f_i = prod_{j in child(i)} f_j cdot g_{|child(i)| + 1}
]
对于(i = rt), 它没有连向父亲的边, 因此
[f_i = prod_{j in child(i)} f_j cdot g_{|child(i)|}
]
答案即为 (f_{rt}).
最后考虑其他的图怎么做:
如果不是仙人掌, 答案为0;
如果图是仙人掌:
对于仙人掌的一个环上的两点 (p) 和 (q), 显然不能再加边使它们在环外联通. 因此, 我们可以去掉所有的环, 对于剩下的每棵树分别求出答案, 对答案相乘即可.
Code
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
using namespace std;
#define rep(i,l,r) for(register int i=(l);i<=(r);++i)
#define repdo(i,l,r) for(register int i=(l);i>=(r);--i)
#define il inline
typedef double db;
typedef long long ll;
//---------------------------------------
const int nsz=5e5+50,msz=1e6+50;
const ll nmod=998244353;
int t,n,m;
struct te{int t,pr,del;}edge[msz*2];
int hd[nsz],pe=1;
#define forg(p,i,v) for(int i=hd[p],v=edge[i].t;i;i=edge[i].pr,v=edge[i].t)
void adde(int f,int t){edge[++pe]=(te){t,hd[f],0};hd[f]=pe;}
void adddb(int f,int t){adde(f,t);adde(t,f);}
ll g[nsz];
void init(int bnd){
g[0]=1,g[1]=1;
rep(i,2,bnd)g[i]=(g[i-1]+g[i-2]*(i-1))%nmod;
}
int vis[nsz],stkp[nsz],stk[nsz],top=0;
bool solcactus(int p,int e0){
stk[++top]=e0^1,stkp[p]=top,vis[p]=1;
forg(p,i,v){
if(i==e0)continue;
if(vis[v]){//cir
if(stkp[v]>stkp[p])continue;
edge[i].del=edge[i^1].del=1;
rep(j,stkp[v]+1,stkp[p]){
if(edge[stk[j]].del)return 0;
edge[stk[j]].del=edge[stk[j]^1].del=1;
}
continue;
}
if(solcactus(v,i^1)==0)return 0;
}
--top;
return 1;
}
ll dp[nsz];
void dfs(int p,int fa){
dp[p]=1,vis[p]=1;
int cnt=0;
forg(p,i,v){
if(v==fa||edge[i].del)continue;
dfs(v,p);
dp[p]=dp[p]*dp[v]%nmod;
++cnt;
}
dp[p]=dp[p]*(fa==0?g[cnt]:g[cnt+1])%nmod;
}
ll sol(){
memset(vis,0,(n+10)*sizeof(int));
top=0;
if(solcactus(1,0)==0)return 0;
memset(vis,0,(n+10)*sizeof(int));
ll res=1;
rep(i,1,n){
if(vis[i]==0)dfs(i,0),res=res*dp[i]%nmod;
}
return res;
}
void init1(int n){
memset(hd,0,(n+10)*sizeof(int));
pe=1;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
init(5e5+50);
cin>>t;
rep(cs,1,t){
cin>>n>>m;
init1(n);
int a,b;
rep(i,1,m)cin>>a>>b,adddb(a,b);
cout<<sol()<<'
';
}
return 0;
}