【ZJOI2017】仙人掌

  • 本文为博主原创，未经许可不得转载

这题非常的神奇

首先如果原图不是仙人掌，那么答案显然是0

然后我们发现原图中的环对答案没有贡献，所以把环删掉之后，原图变成了森林

我们只需要算出每棵树的答案，然后乘起来就行了

那么现在问题就变成了给你一棵树，用边不相交的路径覆盖这颗树，求方案数（这个模型转换要仔细考虑清楚）

设f[x]表示以x为根且没有路径可以往上扩展的子树的答案

g[x]表示路径可以往上扩展的答案

h[x]表示儿子之间的匹配方案

$h[i]=h[i-1]+h[i-2] \times (i-1)$

$f[x]=h[cnt] \prod g[y]$

$g[x]=f[x]+h[cnt-1] \times cnt \prod g[y]$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 500100
#define MAXM 1000100
#define cmin(a,b) a=min(a,b)
#define cmax(a,b) a=max(a,b)
using namespace std;
const int mod=998244353;
struct node{int y,next;}e[MAXM<<1];
int n,m,dfs_clock,len,top,No_Cactus,bcnt,Link[MAXN],dfn[MAXN],low[MAXN],vis[MAXN],st[MAXN],belong[MAXN],h[MAXN],f[MAXN],g[MAXN],check[MAXM<<1];
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(ch>'9'||ch<'0')  {if(ch=='-')  f=-1;  ch=getchar();}
	while(ch>='0'&&ch<='9')  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
inline int add(int a,int b){return (a+=b)>=mod?a-mod:a;}
inline int sub(int a,int b){return (a-=b)<0?a+mod:a;}
inline int mul(int a,int b){return 1LL*a*b%mod;}
void insert(int x,int y){e[++len].next=Link[x];Link[x]=len;e[len].y=y;}
void tarjan(int x,int fa){
	dfn[x]=low[x]=++dfs_clock;  
	st[++top]=x;  vis[x]=1; int cnt=0;
	for(int i=Link[x];i;i=e[i].next)if(e[i].y!=fa){
		if(!dfn[e[i].y]){
			tarjan(e[i].y,x);
			cmin(low[x],low[e[i].y]);
			if(low[e[i].y]<dfn[x]) ++cnt;
		}
		else if(vis[e[i].y]){
			cmin(low[x],dfn[e[i].y]);
			if(low[e[i].y]<dfn[x]) ++cnt;
		}
	}
	if(cnt>=2) No_Cactus=1;
	if(dfn[x]==low[x]){
		int y;  bcnt++;
		do{
			y=st[top--];
			vis[y]=0;
			belong[y]=bcnt;
		}while(x!=y);
	}
}
void dfs(int x,int fa){
	int cnt=0;  f[x]=1;  vis[x]=1;
	for(int i=Link[x];i;i=e[i].next)if(!check[i]&&e[i].y!=fa){
		dfs(e[i].y,x);  ++cnt;
		f[x]=mul(f[x],g[e[i].y]);
	}
	g[x]=mul(mul(f[x],h[cnt-1]),cnt);
	f[x]=mul(f[x],h[cnt]);
	g[x]=add(g[x],f[x]);
}
void clear(){
	dfs_clock=len=bcnt=top=No_Cactus=0;
	for(int i=1;i<=n;++i) Link[i]=dfn[i]=low[i]=vis[i]=belong[i]=0;
}
void solve(){
	n=read();  m=read();  clear();  int ans=1;
	for(int i=1;i<=m;++i){
		int x=read(),y=read();
		insert(x,y);  insert(y,x);
	}
	for(int i=1;i<=len;++i)check[i]=0;
	tarjan(1,0);
	if(No_Cactus) {puts("0");  return;}
	for(int i=1;i<=n;++i)vis[i]=0;
	for(int i=1;i<=n;++i)for(int j=Link[i];j;j=e[j].next)
		if(belong[i]==belong[e[j].y])check[j]=1;
	for(int i=1;i<=n;++i)if(!vis[i]){
		dfs(i,0);
		ans=mul(ans,f[i]);
	}
	printf("%d\n",ans);
}
void pre(){
	h[0]=1;  h[1]=1;  int N=500000;
	for(int i=2;i<=N;++i){
		h[i]=add(h[i],h[i-1]);
		h[i]=add(h[i],mul(h[i-2],i-1));
	}
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	pre();for(int T=read();T;--T) solve();
	return 0;
}

本文标题:【ZJOI2017】仙人掌

文章作者:chty

发布时间:2017年06月11日 - 21时10分

最后更新:2018年06月08日 - 18时50分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
,