给出一张nn个点mm条边的联通图，求图的最大独立集方案数

n≤105,m≤n+10n\le 10^5, m\le n + 10

Luogu P4426

LOJ 2496

Solution

首先考虑树的情况怎么做，设dp[x][0/1]dp[x][0/1]表示x选/不选的方案数，显然有转移：

dp[x][0]=∏y(dp[y][0]+dp[y][1])dp[x][1]=∏ydp[y][0] \begin{aligned} dp[x][0] = &\prod_{y} (dp[y][0] + dp[y][1])\\ dp[x][1] = &\prod_{y} dp[y][0] \end{aligned}

因为非树边比较少，所以可以考虑枚举所有非树边连接的点的状态，显然只有三种情况：(0,1),(0,0),(1,0)(0, 1), (0, 0), (1, 0)

又因为前两种状态可以合并成钦定前一个点必不选这一个状态，复杂度O(2m−n+1n)O(2^{m-n+1}n)

考虑优化这个做法，显然每次枚举状态进行dp可以用虚树优化

把所有非树边连接的点提出来建立虚树，并且对于不同状态，这个虚树的形态是不会变的

因此，我们可以一开始直接把虚树构建出来，只要一个点有至少两棵子树中包含关键点，那么它就是关键点

具体实现上可以记录一个 表示 子树中最深度最浅的关键点是谁

因为这里的dp是一个乘积的形式，所以在处理虚边信息（原树中链）时就需要考虑非虚子树的贡献

这里定义，对于 而言，若它的某个儿子 子树中有关键点，则称 的子树为 的虚子树；否则称其为 的非虚子树

设 表示从 到 这条链上，若 选/不选， 选/不选时， 对于 的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
inline void dfs1 (int x)
{
	g[x][0] = g[x][1] = 1;

	for (int i = Begin[x]; i; i = Next[i])
	{
		int y = To[i];
		if (fa[y] != x) continue;

		dfs1 (y);

		if (!Son[y]) //说明y的子树中没有一个关键点，即y为x的非虚子树
		{//直接把y的贡献统计到x上
			g[x][0] = (LL)g[x][0] * (g[y][0] + g[y][1]) % Mod;
			g[x][1] = (LL)g[x][1] * g[y][0] % Mod;
		}
		else 
		{
            //x继承y的转移系数
			k[x][0] = k[y][0] + k[y][1];
			k[x][1] = k[y][0];

			if (Key[x]) //若x为关键点，则连虚树边 
                VTREE :: add_edge (x, Son[y], k[x][0], k[x][1]);
			else Son[x] = Son[y];
		}
	}

	if (Key[x]) // 清空转移系数
        k[x][0] = mp(1, 0), k[x][1] = mp(0, 1), Son[x] = x;
	else // 把当前点的非虚子树信息乘到转移系数上 
        k[x][0] *= g[x][0], k[x][1] *= g[x][1];
}

幸好这道题不需要对于每次dp都建一遍虚树，不然真的会疯掉。。。

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
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 1e5 + 100, Mod = 998244353;

inline pii operator + (const pii &a, const pii &b) { return mp((a.x + b.x) % Mod, (a.y + b.y) % Mod); }
inline pii operator * (const pii &a, const pii &b) { return mp((LL)a.x * b.x % Mod, (LL)a.y * b.y % Mod); }
inline pii operator * (const pii &a, const int b) { return mp((LL)a.x * b % Mod, (LL)a.y * b % Mod); }
inline void operator += (pii &a, const pii &b) { a = a + b; }
inline void operator *= (pii &a, const int &b) { a = a * b; }
inline void operator *= (pii &a, const pii &b) { a = a * b; }

int N, M;
int e, Begin[Maxn], To[Maxn << 1], Next[Maxn << 1];
int fa[Maxn], Vis[Maxn], extra;
pii E[Maxn];

inline void Add (int &a, int b) { a += b; if (a >= Mod) a -= Mod; }

inline void add_edge (int x, int y) { To[++e] = y; Next[e] = Begin[x]; Begin[x] = e; }

int Key[Maxn], Son[Maxn];

int f[Maxn][2], g[Maxn][2];
pii k[Maxn][2];

namespace VTREE
{
	int Col[Maxn];
	pii k0[Maxn], k1[Maxn];

	int e, Begin[Maxn], To[Maxn << 1], Next[Maxn << 1];

	inline void add_edge (int x, int y, pii a, pii b) { To[++e] = y; Next[e] = Begin[x]; Begin[x] = e; k0[e] = a, k1[e] = b; }

	inline int Calc (pii a, pii b)
	{
		a *= b;
		return (a.x + a.y) % Mod;
	}

	inline void get_dp (int x)
	{
		f[x][0] = g[x][0], f[x][1] = g[x][1];
		if (~Col[x]) f[x][!Col[x]] = 0;

		for (int i = Begin[x]; i; i = Next[i])
		{
			int y = To[i];

			get_dp (y);

			f[x][0] = (LL)f[x][0] * Calc (k0[i], mp(f[y][0], f[y][1])) % Mod;
			f[x][1] = (LL)f[x][1] * Calc (k1[i], mp(f[y][0], f[y][1])) % Mod;
		}
	}

	inline void work ()
	{
		memset(Col, -1, sizeof Col);

		int ALL = (1 << extra) - 1, ans = 0;
		for (int i = 0; i <= ALL; ++i)
		{
			int fl = 0;

			for (int j = 1; j <= extra; ++j) 
				if ((1 << (j - 1)) & i) 
				{
					if (Col[E[j].x] == 0 || Col[E[j].y] == 1) { fl = 1; break; }
					Col[E[j].x] = 1, Col[E[j].y] = 0;
				}
				else 
				{
					if (Col[E[j].x] == 1) { fl = 1; break; }
					Col[E[j].x] = 0;
				}

			if (!fl)
			{
				get_dp (1);
				Add (ans, (f[1][0] + f[1][1]) % Mod);
			}

			for (int j = 1; j <= extra; ++j) Col[E[j].x] = Col[E[j].y] = -1;
		}

		cout << ans << endl;
	}
}

inline int dfs0 (int x)
{
	Vis[x] = 1;
	int cnt = 0;

	for (int i = Begin[x]; i; i = Next[i])
	{
		int y = To[i];
		if (y == fa[x]) continue;

		if (Vis[y])
		{
			Key[x] = 1;
			if (Vis[y] == 1) E[++extra] = mp(y, x);
		}
		else
		{
			fa[y] = x;
			cnt += dfs0(y);
		}
	}

	Vis[x] = 2;
	if (cnt > 1) Key[x] = 1;

	return cnt || Key[x];
}

inline void dfs1 (int x)
{
	g[x][0] = g[x][1] = 1;

	for (int i = Begin[x]; i; i = Next[i])
	{
		int y = To[i];
		if (fa[y] != x) continue;

		dfs1 (y);

		if (!Son[y])
		{
			g[x][0] = (LL)g[x][0] * (g[y][0] + g[y][1]) % Mod;
			g[x][1] = (LL)g[x][1] * g[y][0] % Mod;
		}
		else 
		{
			k[x][0] = k[y][0] + k[y][1];
			k[x][1] = k[y][0];

			if (Key[x]) VTREE :: add_edge (x, Son[y], k[x][0], k[x][1]);
			else Son[x] = Son[y];
		}
	}

	if (Key[x]) k[x][0] = mp(1, 0), k[x][1] = mp(0, 1), Son[x] = x;
	else k[x][0] *= g[x][0], k[x][1] *= g[x][1];
}

inline void Solve ()
{
	Key[1] = 1;
	dfs0 (1), dfs1 (1);
	VTREE :: work ();
}

inline void Input ()
{
	N = read<int>(), M = read<int>();
	for (int i = 1; i <= M; ++i)
	{
		int x = read<int>(), y = read<int>();
		add_edge (x, y);
		add_edge (y, x);
	}
}

int main()
{

#ifndef ONLINE_JUDGE
	freopen("A.in", "r", stdin);
	freopen("A.out", "w", stdout);
#endif

	Input ();
	Solve ();

	return 0;
}