题目大意
给定一个 $n$ 个点 $m$ 条边的无向联通图，你要在图上加若干条不重复的边（可以加 $0$ 条），使得图变成一棵仙人掌。求加边方案数量$\bmod 998244353$ 的结果。
数据范围：$n \le 5 \times 10^5, m \le 10^6$。
思路分析
搞不懂为什么好多题解都要用树形 DP。
首先如果一个图不是仙人掌，那么它加边后也不可能变成一个仙人掌，方案数为 $0$。
对于一个仙人掌，发现加边的两个端点形成的路径上不能经过任何一个环，否则在环上的那条边就会被新加上的那条边形成的新环包含，也就是被两个环包含。所以环不对答案产生影响，我们事先把环上的所有边删去，然后对于留下的每一棵树，计算它单独的方案数，最后乘起来即可。
对于一棵树，进行一个转化：在两个结点之间加一条边转化成覆盖在树上两个结点形成的路径。于是我们发现这条路径包含的边数肯定 $\ge 2$，并且选出的路径的边不能有相交。为了使算法更加简洁，我们将没有被覆盖的边视为被长度为 $1$ 的路径覆盖了。于是问题就转化成了求树上选出一些路径恰好覆盖所有边的方案数。
对于每个结点，我们考虑它的邻边配对的情况。邻边可以单个一组，也就是作为一条路径的端点；或者可以两两配对，也就是作为一条路径中间的某处。记有 $n$ 条邻边的方案数为 $f(n)$，考虑 $f$ 的递推公式。我们新加入 $n$ 号邻边时，对于第一种情况，剩下的邻边随便配，故 $f(n) \leftarrow f(n) + f(n - 1)$。对于第二种情况，新加入的边要和以前的某个边配对，剩下的 $n - 2$ 条边随便配，故 $f(n) \leftarrow f(n) + (n - 1) \times f(n - 2)$。
我们发现对于每个结点方案数不互相影响。所以总方案数为 $\prod f(\text{deg}(i))$。
至此问题得到圆满解决。时间复杂度 $O(n + m)$。
代码实现
如何判断仙人掌呢？我们搞出一棵 DFS 树，然后对于一条返祖边，我们把它两个端点在 DFS 树上的路径 $+1$。最后如果每条边的权值都 $\le 1$，则图是仙人掌。而权值为 $1$ 的边是环上的边。
1 | |
2 | |
3 | using namespace std; |
4 | |
5 | const int maxn = 5e5, mod = 998244353; |
6 | int T, n, m, f[maxn + 3], deg[maxn + 3], dep[maxn + 3], cnt[maxn + 3]; |
7 | vector<int> G[maxn + 3]; |
8 | bool vis[maxn + 3]; |
9 | |
10 | void clear() { |
11 | for (int i = 1; i <= n; i++) { |
12 | G[i].clear(), deg[i] = 0; |
13 | vis[i] = false, cnt[i] = 0; |
14 | } |
15 | } |
16 | |
17 | void add(int u, int v) { |
18 | G[u].push_back(v); |
19 | } |
20 | |
21 | void dfs1(int u, int pa = 0) { |
22 | vis[u] = true; |
23 | for (int i = 0, v; i < G[u].size(); i++) { |
24 | v = G[u][i]; |
25 | if (v == pa) continue; |
26 | if (!vis[v]) { |
27 | dep[v] = dep[u] + 1; |
28 | dfs1(v, u); |
29 | cnt[u] += cnt[v]; |
30 | } else if (dep[u] > dep[v]) { |
31 | cnt[u]++, cnt[v]--; |
32 | } |
33 | } |
34 | } |
35 | |
36 | void dfs2(int u) { |
37 | vis[u] = true; |
38 | for (int i = 0, v; i < G[u].size(); i++) { |
39 | v = G[u][i]; |
40 | if (vis[v]) continue; |
41 | dfs2(v); |
42 | if (!cnt[v]) { |
43 | deg[u]++, deg[v]++; |
44 | } |
45 | } |
46 | } |
47 | |
48 | int main() { |
49 | f[0] = f[1] = 1; |
50 | for (int i = 2; i <= maxn; i++) { |
51 | f[i] = (f[i - 1] + 1ll * f[i - 2] * (i - 1)) % mod; |
52 | } |
53 | scanf("%d", &T); |
54 | while (T--) { |
55 | clear(); |
56 | scanf("%d %d", &n, &m); |
57 | for (int i = 1, u, v; i <= m; i++) { |
58 | scanf("%d %d", &u, &v); |
59 | add(u, v), add(v, u); |
60 | } |
61 | dfs1(1); |
62 | bool flag = false; |
63 | for (int i = 1; i <= n; i++) if (cnt[i] > 1) { |
64 | flag = true; |
65 | } |
66 | if (flag) { |
67 | puts("0"); |
68 | continue; |
69 | } |
70 | for (int i = 1; i <= n; i++) { |
71 | vis[i] = false; |
72 | } |
73 | dfs2(1); |
74 | int ans = 1; |
75 | for (int i = 1; i <= n; i++) { |
76 | ans = 1ll * ans * f[deg[i]] % mod; |
77 | } |
78 | printf("%d\n", ans); |
79 | } |
80 | return 0; |
81 | } |