BZOJ4784 「ZJOI2017」仙人掌

题解
仙人掌, 动态规划

Description

给定一张 $n$ 个点 $m$ 条边的无向简单连通图，问有多少种加边方法使其是一颗仙人掌。

$n \leq 5\cdot 10^5, m \leq \min\{\frac{n\cdot(n+1)}{2}, 10^6\}$

Solution

若原图不是一颗仙人掌，直接输出 $0​$ 即可。

若其是一颗仙人掌，其中的环对答案没有贡献（既不能在其中加边，也不能向外连边），可以直接把与这个环相关的边删掉。剩下的即是一颗森林。求出每棵树的方案数将其直接累乘即可。

如果图是树的情况下怎么做？发现如果在一颗树找出若干个不相交的链，每个链的首尾连一条边，那么这个图一定是仙人掌；反之，最后加完边的图，加上的每一条边都对应一条链，每一条边也只会属于至多一个环即至多属于一个树链加上加上的边。所以问题转化成在一棵树中找出若干不相交的链的方案数。 这样还是不是特别好做，如果我们把那些没有在任何一个环的树边看成在他与他自己的环里，那么问题就转化成了 用若干条不相交的链覆盖整颗树的方案数 。

考虑树形dp。令 $dp_u​$ 为 $u​$ 的子树中所有边加上他到父亲的一条边的方案数。令 $f_x​$ 表示一个点的度数为 $x​$，把所有与它相连的边用长度不超过 $2​$ 的链全部覆盖的方案数，则 $dp_u = f_{deg_u}\Pi _vdp_{v}​$ 。其中 $v​$ 是 $u​$ 的子节点，$deg_u​$ 是 $u​$ 的度数。

$f$ 考虑用递推求。每次新加入一条边，他可以自己是一条链，也可以与之前的一条匹配成一条链。易得 $f_n = f_{n-1}+(n-1)\cdot f_{n-2}$ 并且 $f_0 = f_1= 1$ 。

复杂度 $O(n+m)$

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
/**
 * Author: AcFunction
 * Date:   2019-05-20 22:37:18
 * Email:  3486942970@qq.com
**/

#include <bits/stdc++.h>

using namespace std;

const int N = 500500;
const int M = 1000010;  
const int mod = 998244353; 

int T;
int n, m;
int vis[N], C[N], fa[N], dep[N];
int dp[N], x[N];  

struct Edge {
  int u, v; 
} E[M]; 

struct edge {
  int v; edge *next; 
} pool[M * 2], *h1[N], *h2[N], *h3[N], *cur = pool; 

// h1 : pre ; h2 : tree
// h3 : delete circle
// 

int add(int x, int y) {
  return (x += y) >= mod ? x - mod : x; 
}

void prework() {
  x[0] = x[1] = 1; 
  for(int i = 2; i <= 500000; i++) 
    x[i] = add(x[i - 1], 1ll * (i - 1) * x[i - 2] % mod); 
}

void ade1(int u, int v) {
  edge *p = cur++; p->v = v; 
  p->next = h1[u], h1[u] = p;
}
void ade2(int u, int v) {
  edge *p = cur++; p->v = v; 
  p->next = h2[u], h2[u] = p; 
}

void ade3(int u, int v) {
  edge *p = cur++; p->v = v; 
  p->next = h3[u], h3[u] = p; 
}

void GetTree(int u, int pre) {
  vis[u] = 1; 
  for(edge *p = h1[u]; p; p = p->next) {
    int v = p->v; if(v == pre) continue ; 
    if(vis[v]) continue ; 
    fa[v] = u; dep[v] = dep[u] + 1; 
    GetTree(v, u); 
  }
}

void GetC(int u, int pre) {
  for(edge *p = h2[u]; p; p = p->next) {
    int v = p->v; if(v == pre) continue ;
    GetC(v, u); C[u] += C[v];  
  }
}

void solve(int u, int pre) {
  vis[u] = 1; dp[u] = 1; int cl = 0; 
  for(edge *p = h3[u]; p; p = p->next) {
    int v = p->v; if(v == pre) continue ; 
    if(vis[v]) continue ; 
    solve(v, u); 
    dp[u] = 1ll * dp[u] * dp[v] % mod; ++cl; 
  }
  if(u == pre) dp[u] = 1ll * dp[u] * x[cl] % mod;
  else dp[u] = 1ll * dp[u] * x[cl + 1] % mod;  
}

int main() {
  prework(); 
  scanf("%d", &T); 
  while(T--) {
    scanf("%d %d", &n, &m); 
    for(int i = 1; i <= n; i++) {
      vis[i] = C[i] = dp[i] = dep[i] = 0; 
      h1[i] = h2[i] = h3[i] = 0; 
    } 
    cur = pool; 
    for(int i = 1; i <= m; i++) {
      scanf("%d %d", &E[i].u, &E[i].v);
      ade1(E[i].u, E[i].v), ade1(E[i].v, E[i].u);  
    }
    dep[1] = 1; 
    GetTree(1, 0); 
    for(int i = 1; i <= m; i++) {
      if(dep[E[i].u] < dep[E[i].v]) 
        swap(E[i].u, E[i].v); 
      int u = E[i].u, v = E[i].v; 
      if(fa[u] == v || fa[v] == u) {
        ade2(u, v), ade2(v, u); 
      } 
      else C[u]++, C[v]--; 
    }
    GetC(1, 0); 
    bool isc = 1; 
    for(int i = 1; i <= n; i++) 
      if(C[i] >= 2) {
        isc = 0; break ; 
      }
    if(isc == 0) {
      puts("0"); continue ; 
    }
    for(int i = 1; i <= n; i++)
      vis[i] = 0; 
    for(int i = 1; i <= m; i++) {
      int u = E[i].u, v = E[i].v; 
      if(fa[u] == v || fa[v] == u)
        if(!C[u]) ade3(u, v), ade3(v, u); 
    }
    int ans = 1; 
    for(int i = 1; i <= n; i++) {
      if(!vis[i]) {
        solve(i, i); 
        ans = 1ll * ans * dp[i] % mod; 
      }
    } 
    printf("%d\n", ans); 
  }
  return 0; 
}