abcdeffa's Blog

当局者迷，旁观者清。

0%

LOJ P2250 【仙人掌】

发表于 更新于

Description

给你一个 $n$ 个点 $m$ 条边的无向无重边无自环连通图，问你有多少种加边的方案使其成为一棵仙人掌。

Solution

考虑树形 DP。

考虑如果给定图是一棵树怎么做。

设 $f_i$ 表示以 $i$ 为根的子树的方案数，那么有两种情况可以转移到 $f_i$。

第一种是以儿子为根的子树的方案数的积（子树间互不干扰），第二种是子树间连边。

对于第一种情况，答案显然为 $\prod f_j$，其中点 $j$ 为点 $i$ 的儿子。

对于第二种情况，考虑设 $g_i$ 表示有 $i$ 个儿子的情况下相互连接且向上伸展的方案数。

那么对于第二种情况，答案显然为 $g_{S + [x \not= root]}$，其中 $S$ 为点 $x$ 的儿子个数，$root$ 为根节点的编号。

那么就有 $f_i = (\prod f_j) \times g_{S + [x \not= root]}$。

考虑如果给定图不是树那么怎么做。

容易发现如果给定图不是仙人掌的话那么答案为 0，于是问题就转化成了如果给定图是仙人掌怎么做。

容易发现环对答案是没有贡献的，因为你不能在环内连边使其在连边后还是一棵仙人掌。

那么我们就可以考虑把环边删去，这样我们就得到了一个森林。

那么全局的答案就是每棵树的方案数的乘积了。

因为被 OJ 卡栈空间了，所以我手动扩栈了一下。

Code

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include <cstdio>
#include <cstdlib>
#include <unordered_map>
#define mod 998244353
#define maxN 1000010
long long len = 0, n = 0, m = 0, T = 0;
long long f[maxN], g[maxN];
long long vis[maxN], V[maxN];
long long dep[maxN], dfn[maxN], fa[maxN], h[maxN];
std::unordered_map<int, std::unordered_map<int, int> > notedge;
struct Edge{ long long x, y, g; } b[maxN << 1];
void ins (long long x, long long y)
{
	len++;
	b[len].x = x;
	b[len].y = y;
	b[len].g = h[x];
	h[x] = len;
}
void dfs (long long x, long long p)
{
	dfn[x] = ++dfn[0];
	for(long long i = h[x];i;i = b[i].g)
	{
		long long y = b[i].y;
		if(!dep[y])
		{
			fa[y] = x;
			dep[y] = dep[x] + 1;
			dfs(y, x);
		}
	}
}
bool check ()
{
	dep[1] = 1;
	dfs(1, 0);
	for(long long x = 1;x <= n; x++)
	{
		for(long long i = h[x];i;i = b[i].g)
		{
			long long y = b[i].y;
			if(x > y)
			{
				continue;
			}
			long long u = x, v = y;
			if(dfn[u] < dfn[v])
			{
				long long t = u;
				u = v;
				v = t;
			}
			while(u != v)
			{
				if(vis[u] == 2)
				{
					return false;
				}
				vis[u]++;
				u = fa[u];
			}
		}
	}
	return true;
}
void work (long long x)
{
	for(long long i = h[x];i;i = b[i].g)
	{
		long long y = b[i].y;
		if(V[y] && y != fa[x])
		{
			long long u = x, v = y;
			notedge[u][v] = notedge[v][u] = T + 1;
			while(u != v)
			{
				notedge[u][fa[u]] = notedge[fa[u]][u] = T + 1;
				u = fa[u];
			}
			return ;
		}
		else if(!V[y])
		{
			V[y] = 1;
			work(y);
			V[y] = 0;
		}
	}
}
void dp (long long x, long long fa)
{
	f[x] = V[x] = 1;
	long long soncount = 0;
	for(long long i = h[x];i;i = b[i].g)
	{
		long long y = b[i].y;
		if(!V[y] && notedge[x][y] != T + 1)
		{
			soncount++;
			dp(y, x);
			f[x] *= f[y];
			f[x] %= mod;
		}
	}
	f[x] *= g[soncount + (x != fa)];
	f[x] %= mod;
}
int main ()
{
	freopen("cactus.in", "r", stdin);
	freopen("cactus.out", "w", stdout);
	int size = 256 << 20;
    __asm__("movq %0, %%rsp\n"::"r"((char*)malloc(size)+size));
	scanf("%d", &T);
	while(T--)
	{
		len = 0;
		dfn[0] = 0;
		scanf("%lld %lld", &n, &m);
		for(long long i = 1;i <= n; i++)
		{
			g[i] = 0;
			dfn[i] = dep[i] = vis[i] = V[i] = h[i] = 0;
		}
		for(long long i = 1;i <= m; i++)
		{
			long long x = 0, y = 0;
			scanf("%lld %lld", &x, &y);
			ins(x, y);
			ins(y, x);
		}
		g[0] = g[1] = 1;
		for(long long i = 2;i <= n; i++)
		{
			g[i] = g[i - 1] + ((i - 1) * g[i - 2] % mod);
			g[i] %= mod;
		}
		if(!check())
		{
			printf("0\n");
			continue;
		}
		V[1] = 1;
		work(1);
		for(long long i = 1;i <= n; i++)
		{
			V[i] = 0;
		}
		long long Ans = 1;
		for(long long i = 1;i <= n; i++)
		{
			if(!V[i])
			{
				dp(i, i);
				Ans *= f[i];
				Ans %= mod;
			}
		}
		printf("%lld\n", Ans);
	}
	exit(0);
}