题目大意

「SDOI 2018」战略游戏（Luogu 4606）

给定 $n$ 个点 $m$ 条边的无向图，$q$ 次询问，每次询问点集 $S$，求图中有多少个点满足删掉它之后 $S$ 中至少两个点不联通。

$n, q \le 10^5, m, \sum \vert S \vert \le 2 \times 10^5$。

思路分析

圆方树上建虚树，欢乐多又多

其实这是广义圆方树和虚树的学习笔记。

不难发现答案为 $S$ 在广义圆方树上形成的虚树中的圆点个数减去 $\vert S \vert$。建出广义圆方树和虚树即可。

时间复杂度 $O(n \log n)$。

代码实现

1	#include <cstdio>
2	#include <vector>
3	#include <algorithm>
4	using namespace std;
5
6	const int maxn = 1e5, maxm = 2 * maxn, maxk = 2 * maxm, logk = 18;
7	int T, n, m, q, tm, cnt, dfn[maxn + 3], low[maxn + 3], top, st[maxm + 3];
8	int tot, ter[maxk + 3], nxt[maxk + 3], lnk[maxn + 3];
9	int tm_t, dfn_t[maxm + 3], dep[maxm + 3], fa[maxm + 3], sz[maxm + 3];
10	int pnt[maxk + 3][logk + 3], lg[maxk + 3], id[maxm + 3], ans;
11	bool vis[maxn + 3];
12	vector<int> G[maxm + 3];
13
14	void add(int u, int v) {
15	ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot;
16	}
17
18	void add_vec(int u, int v) {
19	G[u].push_back(v), G[v].push_back(u);
20	}
21
22	void tarjan(int u) {
23	dfn[u] = low[u] = ++tm;
24	vis[u] = true, st[++top] = u;
25	for (int i = lnk[u], v; i; i = nxt[i]) {
26	v = ter[i];
27	if (!dfn[v]) {
28	tarjan(v);
29	low[u] = min(low[u], low[v]);
30	if (low[v] >= dfn[u]) {
31	add_vec(++cnt, u);
32	do {
33	add_vec(cnt, st[top]);
34	} while (st[top--] != v);
35	}
36	} else {
37	low[u] = min(low[u], dfn[v]);
38	}
39	}
40	vis[u] = false;
41	}
42
43	void dfs_t(int u, int pa = 0) {
44	dfn_t[u] = ++tm_t;
45	pnt[tm_t][0] = u;
46	sz[u] = sz[pa] + (u <= n);
47	for (int i = 0, v; i < G[u].size(); i++) {
48	v = G[u][i];
49	if (v == pa) continue;
50	dep[v] = dep[u] + 1;
51	fa[v] = u;
52	dfs_t(v, u);
53	pnt[++tm_t][0] = u;
54	}
55	}
56
57	int lca(int a, int b) {
58	a = dfn_t[a], b = dfn_t[b];
59	if (a > b) swap(a, b);
60	int c = lg[b - a + 1];
61	a = pnt[a][c], b = pnt[b - (1 << c) + 1][c];
62	if (dep[a] <= dep[b]) return a;
63	else return b;
64	}
65
66	bool comp(int i, int j) {
67	return dfn_t[i] < dfn_t[j];
68	}
69
70	void insert(int x) {
71	if (x == st[1]) return;
72	int y = lca(x, st[top]);
73	if (y != st[top]) {
74	while (top > 1 && dfn_t[y] < dfn_t[st[top - 1]]) {
75	ans += sz[st[top]] - sz[st[top - 1]], top--;
76	}
77	if (dfn_t[y] > dfn_t[st[top - 1]]) {
78	ans += sz[st[top]] - sz[y];
79	st[top] = y;
80	} else {
81	ans += sz[st[top--]] - sz[y];
82	}
83	}
84	st[++top] = x;
85	}
86
87	int main() {
88	scanf("%d", &T);
89	while (T--) {
90	scanf("%d %d", &n, &m);
91	tot = 0, fill(lnk + 1, lnk + n + 1, 0);
92	for (int i = 1, u, v; i <= m; i++) {
93	scanf("%d %d", &u, &v);
94	add(u, v), add(v, u);
95	}
96	tm = tm_t = 0;
97	fill(dfn + 1, dfn + n + 1, 0);
98	cnt = n, top = 0;
99	for (int i = 1; i <= 2 * n; i++) {
100	G[i].clear();
101	}
102	for (int i = 1; i <= n; i++) if (!dfn[i]) {
103	tarjan(i);
104	}
105	dfs_t(1);
106	for (int i = 2; i <= tm_t; i++) {
107	lg[i] = lg[i / 2] + 1;
108	}
109	for (int k = 1; 1 << k <= tm_t; k++) {
110	for (int i = 1, j = (1 << (k - 1)) + 1; i <= tm_t - (1 << k) + 1; i++, j++) {
111	if (dep[pnt[i][k - 1]] <= dep[pnt[j][k - 1]]) pnt[i][k] = pnt[i][k - 1];
112	else pnt[i][k] = pnt[j][k - 1];
113	}
114	}
115	scanf("%d", &q);
116	while (q--) {
117	scanf("%d", &m);
118	for (int i = 1; i <= m; i++) {
119	scanf("%d", &id[i]);
120	}
121	int x = lca(id[1], id[2]);
122	for (int i = 3; i <= m; i++) {
123	x = lca(x, id[i]);
124	}
125	sort(id + 1, id + m + 1, comp);
126	top = 0, ans = (x <= n) - m;
127	st[++top] = x;
128	for (int i = 1; i <= m; i++) {
129	insert(id[i]);
130	}
131	for (int i = 1; i < top; i++) {
132	ans += sz[st[i + 1]] - sz[st[i]];
133	}
134	printf("%d\n", ans);
135	}
136	}
137	return 0;
138	}