[Gym102538G] Giant Penguin

做法

神仙题,看题解了。

取任意一个生成树,取这个树的重心和所有跨过这个重心的非树边的端点(实际上两个端点中只要任取一个就行,只要保证子树不连通),考虑跨过这些点的路径,然后再对每个子树点分。

注意不要把这些点删掉再对每个连通块做点分治,因为这样可能一个连通块不是一个树上连通块,就不是很好处理(应该也能处理)。

然后就像动态点分治一样维护就行,预处理一下要删去的点与当前连通块中每个点的最短距离。

时间复杂度 \(\mathcal O(nk\log n)\)

代码

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
#include <bits/stdc++.h>

using namespace std;

const int maxn = 100010;
const int maxm = 200010;

typedef long long ll;

int n, m, k, q;
int l[maxn], e;

struct Edge {
int v, x;
} E[maxm<<1];

vector<int> tree[maxn];

ll getid(int x, int y) {
return 1LL * (n+1) * x + y;
}

inline void addEdge(int u, int v) {
E[e].v = v, E[e].x = l[u], l[u] = e++;
}

int fT_vis[maxn];
void findTree(int u) {
fT_vis[u] = 1;
for (int p = l[u]; p >= 0; p = E[p].x) {
int v = E[p].v;
if (!fT_vis[v]) {
findTree(v);
tree[u].push_back(v);
tree[v].push_back(u);
}
}
}

int par[maxn], ind[maxn], tot, col[maxn]; // 点分树上父亲,一个点被删掉时对应点分树上哪个点
vector<int> vimp[maxn], mn[maxn]; // 点分树上一次删去的点,以及到连通块内最近被 mark 点的距离
unordered_map<ll, int> mdis; // 被删去的点到内部一个点的距离
int vis[maxn], dep[maxn], sz[maxn], mx[maxn], _vis[maxn], _tim, __vis[maxn], __tim; // 点分治用变量

void dfs1(int u, int f, vector<int> &vl) {
sz[u] = 1, mx[u] = 0;
vl.push_back(u); __vis[u] = __tim;
for (int i = 0; i < tree[u].size(); i++) {
int v = tree[u][i];
if (v != f && !vis[v]) {
dfs1(v, u, vl);
sz[u] += sz[v];
mx[u] = max(mx[u], sz[v]);
}
}
}

void dfs2(int u, int f, int c) {
col[u] = c;
for (int i = 0; i < tree[u].size(); i++) {
int v = tree[u][i];
if (v != f && !vis[v]) {
dfs2(v, u, c);
}
}
}

void dfs3(int u, int f, int &s) {
++ s; _vis[u] = _tim;
for (int i = 0; i < tree[u].size(); i++) {
int v = tree[u][i];
if (v != f && _vis[v] < _tim && !vis[v]) {
dfs3(v, u, s);
}
}
}

int solve(int u, int s) {
int id = ++ tot;
++ __tim;
vector<int> vl;
dfs1(u, 0, vl);
int c = 0;
for (int i = 0; i < vl.size(); i++) {
int x = vl[i];
mx[x] = max(mx[x], s - sz[x]);
if (!c || mx[x] < mx[c]) c = x;
}
vimp[id].push_back(c);
col[c] = c;
for (int i = 0; i < tree[c].size(); i++) {
int v = tree[c][i];
if (!vis[v]) {
dfs2(v, c, v);
}
}
for (int i = 0; i < vl.size(); i++) {
int x = vl[i]; if (x == c) continue;
for (int p = l[x]; p >= 0; p = E[p].x) {
int v = E[p].v;
if (col[x] != col[v] && __vis[v] == __tim) {
if (v == c && col[x] == x) continue;
vimp[id].push_back(min(x, v));
}
}
}
sort(vimp[id].begin(), vimp[id].end());
vimp[id].erase(unique(vimp[id].begin(), vimp[id].end()), vimp[id].end());
mn[id] = vector<int>(vimp[id].size(), 0x3f3f3f3f);
for (int i = 0; i < vimp[id].size(); i++) {
int x = vimp[id][i];
ind[x] = id;
++ _tim;
queue<int> q; q.push(x); _vis[x] = _tim; dep[x] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
if (!mdis.count(getid(x, u))) mdis[getid(x, u)] = 0x3f3f3f3f;
mdis[getid(x, u)] = min(mdis[getid(x, u)], dep[u]);
for (int p = l[u]; p >= 0; p = E[p].x) {
int v = E[p].v;
if (!vis[v] && _vis[v] < _tim && __vis[v] == __tim) {
_vis[v] = _tim;
dep[v] = dep[u] + 1;
q.push(v);
}
}
}
}
++ _tim;
vis[c] = 1, _vis[c] = _tim;
// 原本这里是把所有处理的点删掉的,写得可能有点奇怪,懒得改了
vector<int> vv, vs;
for (int i = 0; i < vl.size(); i++) {
int x = vl[i];
if (_vis[x] < _tim) {
int _s = 0;
dfs3(x, 0, _s);
vv.push_back(x);
vs.push_back(_s);
}
}
for (int i = 0; i < vv.size(); i++) {
par[solve(vv[i], vs[i])] = id;
}
return id;
}

void mark(int u) {
int x = ind[u];
while (x) {
for (int i = 0; i < vimp[x].size(); i++) {
int v = vimp[x][i];
mn[x][i] = min(mn[x][i], mdis[getid(v, u)]);
}
x = par[x];
}
}

int cal(int u) {
int ret = 0x3f3f3f3f;
int x = ind[u];
while (x) {
for (int i = 0; i < vimp[x].size(); i++) {
int v = vimp[x][i];
ret = min(ret, mdis[getid(v, u)] + mn[x][i]);
}
x = par[x];
}
return ret;
}

int main() {
memset(l, -1, sizeof(l));
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= m; i++) {
int u, v; scanf("%d%d", &u, &v);
addEdge(u, v), addEdge(v, u);
}
findTree(1);
solve(1, n);
scanf("%d", &q);
for (int i = 1; i <= q; i++) {
int t, v; scanf("%d%d", &t, &v);
if (t == 1) {
mark(v);
} else printf("%d\n", cal(v));
}
return 0;
}