【仙人掌+树形dp】仙人掌

仙人掌, 动态规划DP, 图论

传送仙人掌：UOJ190

ZJOI2017

讲道理这道题我考场上可能是爆0了。。。（读优写挂我也是很无奈，不然30分）

先放一张萌萌哒仙人掌（这似乎是这个hexo主题的图，是不是很搭）

cactus

思路：终于进入正题

  • 链的做法还是比较sb的，dp可做，直接找规律也是可以的，反正是2的幂次。
    • 然后考虑树的做法，两点$(u,v)$之间的连边可以看作是一条覆盖了$(u,lca(u,v)),(v,lca(u,v))$的链
    • 可以发现这道题有一个要求是没有重边，这个性质可就厉害了。可以发现在一个合法的仙人掌（合法的答案），一定是原树上的每条边要么被长度>2的链覆盖，要么不被覆盖。 可以把不覆盖强行当做是被长度为1的链覆盖，因为实际上不存在长度为1的链，所以计数上不会有影响。 这样题意就转化为了求用链恰好覆盖整棵树一次的方案数。
    • 考虑树形dp，用$f_i$表示i（i不为根）及其子树的边和父边被覆盖且恰有一条链连向子树外某点的方案数（不考虑连向外面的是哪个点）：
      • 为什么这么设计状态呢？可以发现对于一棵不是根节点i及其子树，子树内（包括i）总有且一条链是连向子树外的。如果不连出去，i所对应的父边就不被覆盖了；如果连出去多条，i所对应的父边就被多次覆盖。
      • 那么怎么$f_i$转移呢？
      • 首先i的子树是相对独立的，换句话说每棵子树内部的连边与其他子树无关，每棵子树只有连出去的边才能与其他子树连边或是连到i的外面。考虑到$f_i​$的意义，若干棵子树中必须选出一棵来连向i子树的外面，其余的一部分连向i，另一部分相互两两配对。可以发现最终配对的结果与只与子树的棵树有关。
      • 那么$f_i = k\times g_{k-1} \times \prod\limits_{j\in child(i)} f_j$，其中k表示i的子树的棵树；
      • $g_k$表示的k条边在内部两两配对或连到i的方案数，那么k-1是因为一条边强制连到外面
      • $g_k=g_{k-1}+g_{k-2}\times(k-1)$，因为新加进来的边连到根节点的贡献是$g_{k-1}$，配对的话要挑出一条已有的边来配对，贡献是$g_{k-2}\times(k-1)$，这个可以预处理一发。
      • 根的话不用连出去，自己推一下。
    • 至此树的dp没了。
    • 可能是假的，因为这个dp方程显然可以直接分解成乘法，$ans=\prod g_x$。讲道理我是看UOJ上的代码发现的。
    • 然后考虑仙人掌，如果不是仙人掌那显然是GG的。特判一发。
    • 是仙人掌的话可以发现环上的边是没有救的。
    • 所以把环边删掉以后仙人掌就变成了森林，乘法原理。
    • 重点可能是找仙人掌吧！

注意：取模不要忘，预处理注意时间啊（题目有说t很大然而我瞎）

还是贴代码吧：

正常树形dp：

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define LL long long
#define N 2200000
#define mo 998244353
LL t,n,m,x,y,tot,head[N],f[N],g[N],fa[N],mark[N];
bool vis[N],vis2[N];
struct edge{LL v,nxt;}e[N];
LL getint(){
	char ch; LL sum=0;
	for (ch=getchar();ch<'0' || ch>'9';ch=getchar());
	for (;ch>='0' && ch<='9';ch=getchar()) sum=sum*10+ch-'0';
	return sum;
}
void add(LL x,LL y){e[++tot].v=y; e[tot].nxt=head[x]; head[x]=tot;}
void init(LL n){tot=1;	for (int i=1;i<=n;i++){vis[i]=head[i]=mark[i]=fa[i]=vis2[i]=0; f[i]=1;}}
bool dfs(int u){//判定仙人掌+标记环边
	vis[u]=1;
	for (int i=head[u];i;i=e[i].nxt){
		int v=e[i].v;
		if (v==fa[u]) continue;
		if (!vis[v]){fa[v]=u; if (dfs(v)) return 1;}
		else{
			e[i^1].v=fa[v];//防止找到环以后反着又找到了
			for (int k=u;k!=v;k=fa[k]){
				if (mark[k]) return 1; else mark[k]=1;//已经到过的环GG
			}
		}
	}
	return 0;
}
void dp(LL u){
	int sum=0; vis2[u]=1;
	for (int i=head[u];i;i=e[i].nxt){
		int v=e[i].v;
		if (fa[u]==v || vis2[v]) continue; 
		dp(v);
		if (!mark[v]){sum++; f[u]=f[u]*f[v]%mo;}
	}
	if (sum!=0){
		if (fa[u]==0 || mark[u]) f[u]=f[u]*g[sum]%mo;//某棵树的根
		else f[u]=f[u]*(g[sum-1]*sum%mo+g[sum])%mo;//某棵树的子树的根
	}
}
		
int main(){
	t=getint();
	while (t--){
		n=getint(); m=getint();
		init(n);
		g[0]=g[1]=1; for (int i=2;i<=n;i++) g[i]=(g[i-1]+g[i-2]*(i-1))%mo;//预处理
		for (int i=1;i<=m;i++){
			x=getint(); y=getint();
			add(x,y); add(y,x);
		}
		if (dfs(1)){puts("0"); continue;};
		dp(1); LL ans=f[1];
		for (int i=2;i<=n;i++) if (mark[i]) ans=ans*f[i]%mo;
		printf("%lld\n",ans);
	}
	
	
	return 0;
}

强行换成乘法：

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define LL long long
#define N 2200000
#define mo 998244353
LL t,n,m,x,y,tot,head[N],cnt[N],g[N],fa[N],mark[N];
bool vis[N];
struct edge{LL v,nxt;}e[N];
LL getint(){
	char ch; LL sum=0;
	for (ch=getchar();ch<'0' || ch>'9';ch=getchar());
	for (;ch>='0' && ch<='9';ch=getchar()) sum=sum*10+ch-'0';
	return sum;
}
void add(LL x,LL y){e[++tot].v=y; e[tot].nxt=head[x]; head[x]=tot;}
void init(LL n){tot=1;	for (int i=1;i<=n;i++) vis[i]=head[i]=mark[i]=fa[i]=cnt[i]=0;}
bool dfs(int u){
	vis[u]=1;
	for (int i=head[u];i;i=e[i].nxt){
		int v=e[i].v;
		if (v==fa[u]) continue;
		if (!vis[v]){fa[v]=u; if (dfs(v)) return 1;}
		else{
			e[i^1].v=fa[v];
			for (int k=u;k!=v;k=fa[k]){
				if (mark[k]) return 1; else mark[k]=1;
			}
		}
	}
	return 0;
}
		
int main(){
	t=getint();
	while (t--){
		n=getint(); m=getint();
		init(n);
		g[0]=g[1]=1; for (int i=2;i<=n;i++) g[i]=(g[i-1]+g[i-2]*(i-1))%mo;
		for (int i=1;i<=m;i++){
			x=getint(); y=getint();
			add(x,y); add(y,x);
		}
		if (dfs(1)){puts("0"); continue;};
		
		for (int i=2;i<=n;i++) if (!mark[i]){cnt[i]++; cnt[fa[i]]++;}//统计子节点个数
		LL ans=1;
		for (int i=1;i<=n;i++) ans=ans*g[cnt[i]]%mo;//每个节点本身的贡献实际上是子节点的个数带来的
		printf("%lld\n",ans);
	}
	
	
	return 0;
}