BZOJ5329 [SDOI2018] 战略游戏

发表于 | 分类于 | 阅读次数:

Description

一个 \(n\) 个点 \(m\) 条边的无向连通图，\(q\) 次询问。每次询问给出一个集合 \(S\) ，问有多少结点 \(x\) 满足：

  1. \(x\not\in S\);
  2. 删除结点 \(x\) 及与其相连的所有边之后， \(S\) 中的点不连通。

\(n,q\leqslant10^5;m,\sum|S|\leqslant2\times10^5\) 。

多组数据，数组组数 \(T\leqslant10\) ；时限 \(10s\) 。

Solution

首先，删除某结点后 \(x\) 和 \(y\) 不连通，这等价于这个结点在所有 \(x\) 到 \(y\) 的简单路径上。

圆方树基本性质：原图上 \(x\) 到 \(y\) 的所有简单路径交即为圆方树上 \(x\) 到 \(y\) 的所有圆点。

那么我们建出圆方树；可以发现答案就是点集 \(S\) 建出的虚树中除 \(S\) 里所有点之外的圆点个数。

所以暴力建一遍虚树就可以了。时间复杂度 \(O(n\log n+\sum(|S|\log|S|))\) （ RMQ\(O(1)\)LCA ）。

考场上 yy 出一个正确的点双结果由于 RMQ 数组开小爆零了… 。

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
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
 
const int L = 10000000;
inline char getChar() {
  static char s[L], *end = s, *p = s;
  if (p == end) {
    if (feof(stdin)) return EOF;
    end = s + fread(p = s, 1, L, stdin);
  }
  return *(p++);
}
 
int readInt() {
  int ans = 0, c;
  while (!isdigit(c = getChar()));
  do ans = ans * 10 + c - '0';
  while (isdigit(c = getChar()));
  return ans;
}
 
char s[L], *p = s, *end = s + L;
inline void putChar(char c) {
  if (p == end) fwrite(p = s, 1, L, stdout);
  *(p++) = c;
}
 
void printInt(int x, char c = ' ') {
  if (x >= 10) printInt(x / 10, EOF);
  putChar(x % 10 + '0');
  if (c != EOF) putChar(c);
}
 
const int N = 100050;
const int M = 400050;
 
int n, m, pre[N], nxt[M], to[M], cnt;
 
inline void addEdge(int x, int y) {
  nxt[cnt] = pre[x];
  to[pre[x] = cnt++] = y;
  nxt[cnt] = pre[y];
  to[pre[y] = cnt++] = x;
}
 
namespace Tree{
const int N = 200050;
 
int n, pre[N], nxt[N * 2], to[N * 2], cnt;
bool ty[N]; // true: circle; false: square
 
inline void addEdge(int x, int y) {
  nxt[cnt] = pre[x];
  to[pre[x] = cnt++] = y;
  nxt[cnt] = pre[y];
  to[pre[y] = cnt++] = x;
}
 
int dep2[N], pos[N], dep[N], nd[N * 2], cnt2;
 
void dfs(int x, int fa) {
  dep2[x] = dep2[fa] + ty[x];
  nd[pos[x] = ++cnt2] = x;
  dep[x] = dep[fa] + 1;
  for (int i = pre[x]; i >= 0; i = nxt[i])
    if (to[i] != fa) {
      dfs(to[i], x);
      nd[++cnt2] = x;
    }
}
 
inline int mind(int x, int y) { return dep[x] < dep[y] ? x : y; }
 
int minv[20][N * 2], log2[N * 2];
 
void InitRMQ() {
  for (int i = 1; i <= cnt2; ++i) minv[0][i] = nd[i];
  for (int i = 1; (1 << i) <= cnt2; ++i)
    for (int j = 1; (j + (1 << i)) <= cnt2 + 1; ++j)
      minv[i][j] = mind(minv[i - 1][j], minv[i - 1][j + (1 << (i - 1))]);
  for (int i = 1, j = 0; i <= cnt2; ++i)
    log2[i] = j += (i >= (1 << (j + 1)));
}
 
inline int LCA(int x, int y) {
  if ((x = pos[x]) > (y = pos[y])) std::swap(x, y);
  int k = log2[y - x + 1];
  return mind(minv[k][x], minv[k][y - (1 << k) + 1]);
}
 
inline int count(int x, int y) {
  int l = LCA(x, y);
  return dep2[x] + dep2[y] - 2 * dep2[l] + ty[l] - ty[x] - ty[y];
}
 
bool cmp(int a, int b) { return pos[a] < pos[b]; } 
 
int A[N];
int stack[N], top;
 
void Solve() {
  cnt2 = 0;
  dfs(1, 0);
  InitRMQ();
  int q = readInt();
  while (q--) {
    int s = readInt();
    for (int i = 0; i < s; ++i) A[i] = readInt();
    std::sort(A, A + s, cmp);
    int ans = 0;
    top = 0;
    for (int i = 0; i < s; ++i) {
      int x = A[i];
      while (top > 1 && LCA(stack[top - 2], x) == LCA(stack[top - 1], x)) {
        ans += count(stack[top - 2], stack[top - 1]);
        --top;
      }
      if (top > 0) {
        int l = LCA(stack[top - 1], x);
        if (l != stack[top - 1]) {
          ans += count(stack[top - 1], l) + ty[l];
          stack[top - 1] = l;
        }
      }
      stack[top++] = x;
    }
    while (top > 1) ans += count(stack[top - 2], stack[top - 1]), --top;
    printInt(ans, '\n');
  }
}
};
 
int dfn[N], cnt2;
int stack[N], top, bcnt;
 
int Tarjan(int x, int fa) {
  int lowx = dfn[x] = ++cnt2;
  stack[top++] = x;
  for (int i = pre[x]; i >= 0; i = nxt[i])
    if (to[i] != fa) {
      if (dfn[to[i]] == 0) lowx = std::min(lowx, Tarjan(to[i], x));
      else lowx = std::min(lowx, dfn[to[i]]);
    }
  if (lowx >= dfn[fa]) {
    int nn = n + (++bcnt);
    Tree::ty[nn] = false;
    Tree::addEdge(x, nn);
    if (fa > 0) Tree::addEdge(fa, nn);
    while (stack[--top] != x) Tree::addEdge(stack[top], nn);
  }
  return lowx;
}
 
int main() {
  //freopen("game.in", "r", stdin);
  //freopen("game.out", "w", stdout);
  int T = readInt();
  while (T--) {
    n = readInt();
    m = readInt();
    memset(pre, -1, sizeof pre);
    memset(Tree::pre, -1, sizeof Tree::pre);
    cnt = Tree::cnt = 0;
    for (int i = 0; i < m; ++i)
      addEdge(readInt(), readInt());
    for (int i = 1; i <= n; ++i) Tree::ty[i] = true;
    memset(dfn, 0, sizeof dfn);
    top = bcnt = 0;
    Tarjan(1, 0);
    Tree::n = n + bcnt;
    Tree::Solve();
  }
  fwrite(s, 1, p - s, stdout);
  return 0;
}