NekoMio's Blog

美しいものが起こることを常に信じている

  1. 1. Description
  2. 2. Input
  3. 3. Output
  4. 4. Sample Input
  5. 5. Sample Output
  6. 6. HINT

Description

  捉迷藏 Jiajia和Wind是一对恩爱的夫妻,并且他们有很多孩子。某天,Jiajia、Wind和孩子们决定在家里玩
捉迷藏游戏。他们的家很大且构造很奇特,由N个屋子和N-1条双向走廊组成,这N-1条走廊的分布使得任意两个屋
子都互相可达。游戏是这样进行的,孩子们负责躲藏,Jiajia负责找,而Wind负责操纵这N个屋子的灯。在起初的
时候,所有的灯都没有被打开。每一次,孩子们只会躲藏在没有开灯的房间中,但是为了增加刺激性,孩子们会要
求打开某个房间的电灯或者关闭某个房间的电灯。为了评估某一次游戏的复杂性,Jiajia希望知道可能的最远的两
个孩子的距离(即最远的两个关灯房间的距离)。 我们将以如下形式定义每一种操作: C(hange) i 改变第i个房
间的照明状态,若原来打开,则关闭;若原来关闭,则打开。 G(ame) 开始一次游戏,查询最远的两个关灯房间的
距离。

Input

  第一行包含一个整数N,表示房间的个数,房间将被编号为1,2,3…N的整数。接下来N-1行每行两个整数a, b,
表示房间a与房间b之间有一条走廊相连。接下来一行包含一个整数Q,表示操作次数。接着Q行,每行一个操作,如
上文所示。

Output

  对于每一个操作Game,输出一个非负整数到hide.out,表示最远的两个关灯房间的距离。若只有一个房间是关
着灯的,输出0;若所有房间的灯都开着,输出-1。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
8
1 2
2 3
3 4
3 5
3 6
6 7
6 8
7
G
C 1
G
C 2
G
C 1
G

Sample Output

1
2
3
4
4
3
3
4

HINT

对于100%的数据, N ≤100000, M ≤500000。

动态点分治
将每次点分治中的重心建树
在每个点维护值
本题维护两个堆
C[i] 维护子树中的黑点到起分治父亲的Dis
B[i] 维护子树中C[i]的堆顶

ans 维护答案

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
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
#pragma GCC optimize("O3")
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <iostream>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='0')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int MAXN = 100005;
struct Priority_queue
{
__gnu_pbds::priority_queue<int, less<int>, __gnu_pbds::binary_heap_tag> Q1, Q2;
inline int size()
{
return Q1.size() - Q2.size();
}
inline void push(const int &x)
{
Q1.push(x);
}
inline void erase(const int &x)
{
Q2.push(x);
}
inline int top()
{
while (!Q2.empty() && Q1.top() == Q2.top())
{
Q1.pop();
Q2.pop();
}
if (!Q1.empty()) return Q1.top();
else return 0;
}
inline int top2()
{
if (size() < 2) return 0;
while (!Q2.empty() && Q1.top() == Q2.top())
{
Q1.pop();
Q2.pop();
}
int tmp = Q1.top(); Q1.pop();
while (!Q2.empty() && Q1.top() == Q2.top())
{
Q1.pop();
Q2.pop();
}
int ans = Q1.top(); Q1.push(tmp);
return ans;
}
}B[MAXN], C[MAXN], ans;
struct edge
{
int END, next;
}v[MAXN << 1];
int first[MAXN], p;
inline void add(int a, int b)
{
v[p].END = b;
v[p].next = first[a];
first[a] = p++;
}
int f[MAXN][18];
int dep[MAXN];
inline void PreDFS(int rt, int fa)
{
dep[rt] = dep[fa] + 1;
f[rt][0] = fa;
for (int i = 1; i <= 17; i++) f[rt][i] = f[f[rt][i - 1]][i - 1];
for (int i = first[rt]; i != -1; i = v[i].next)
{
if (v[i].END == fa) continue;
PreDFS(v[i].END, rt);
}
}
int sum, Max[MAXN], size[MAXN], root;
bool vis[MAXN];
static inline void GetRoot(int rt, int fa)
{
size[rt] = 1; Max[rt] = 0;
for (int i = first[rt]; i != -1; i = v[i].next)
{
if (vis[v[i].END] || v[i].END == fa) continue;
GetRoot(v[i].END, rt);
size[rt] += size[v[i].END];
Max[rt] = max(Max[rt], size[v[i].END]);
}
Max[rt] = max(Max[rt], sum - size[rt]);
if (Max[rt] < Max[root]) root = rt;
}
int Fa[MAXN];
static inline void Divide(int rt, int fa)
{
vis[rt] = 1;
Fa[rt] = fa;
// cerr << rt << endl;
for (int i = first[rt]; i != -1; i = v[i].next)
{
if (vis[v[i].END]) continue;
sum = size[v[i].END], root = 0;
GetRoot(v[i].END, 0);
Divide(root, rt);
}
}
static inline int LCA(int a, int b)
{
if (dep[a] < dep[b]) swap(a, b);
int d = dep[a] - dep[b];
for (int i = 17; i >= 0; i--)
if (d & (1 << i))
d -= (1 << i), a = f[a][i];
if (a == b) return a;
for (int i = 17; i >= 0; i--)
if (f[a][i] != f[b][i])
a = f[a][i], b = f[b][i];
return f[a][0];
}
static inline int dis(const int &a, const int &b)
{
return dep[a] + dep[b] - 2 * dep[LCA(a, b)];
}
int Color[MAXN];
static inline void Change_To_Black(const int &Height_root, const int &Child)
{
if (Height_root == Child)
{
B[Height_root].push(0);
if (B[Height_root].size() == 2)
ans.push(B[Height_root].top());
}
if (!Fa[Height_root]) return;
int Father = Fa[Height_root];
int Dis = dis(Father, Child);
int tmp = C[Height_root].top();
C[Height_root].push(Dis);
if (Dis > tmp)
{
int size = B[Father].size();
int tmp2 = B[Father].top() + B[Father].top2();
if (tmp)
B[Father].erase(tmp);
B[Father].push(Dis);
int now = B[Father].top() + B[Father].top2();
if (now > tmp2)
{
if (size >= 2) ans.erase(tmp2);
if (B[Father].size() >= 2)
ans.push(now);
}
}
Change_To_Black(Father, Child);
}
static inline void Change_To_White(const int &Height_root, const int &Child)
{
if (Height_root == Child)
{
if (B[Height_root].size() == 2)
ans.erase(B[Height_root].top());
B[Height_root].erase(0);
}
if (!Fa[Height_root]) return;
int Father = Fa[Height_root];
int Dis = dis(Father, Child);
int tmp = C[Height_root].top();
C[Height_root].erase(Dis);
if (tmp == Dis)
{
int size = B[Father].size();
int tmp2 = B[Father].top() + B[Father].top2();
B[Father].erase(Dis);
if (C[Height_root].top())
B[Father].push(C[Height_root].top());
int now = B[Father].top() + B[Father].top2();
if (now < tmp2)
{
if (size >= 2)
ans.erase(tmp2);
if (B[Father].size() >= 2)
ans.push(now);
}
}
Change_To_White(Father, Child);
}
int main()
{
memset (first, -1, sizeof (first));
int n = read();
for (int i = 1; i < n; i++)
{
int a = read(), b = read();
add(a, b);
add(b, a);
// cerr << i << endl;
}
PreDFS(1, 0);

Max[0] = sum = n;
GetRoot(1, 0);

Divide(root, 0);
// cerr << "11!!" << endl;
for (int i = 1; i <= n; i++)
{
Color[i] = 1;
// cerr << i << endl;
C[i].push(0);
// Change_To_Black(i, i);
}
for (int i = 1; i <= n; i++)
{
Change_To_Black(i, i);
// cerr << i << endl;
}
// for (int i = 1; i <= n; i++) cerr << "i fa is " << Fa[i] << endl;
int m = read();
char s[10];
for (int i = 1; i <= m; i++)
{
// cerr << i << endl;
scanf ("%s", s);
if (s[0] == 'C')
{
int k = read();
if (Color[k])
{
Color[k] = 0;
Change_To_White(k, k);
}
else
{
Color[k] = 1;
Change_To_Black(k, k);
}
}
else
printf ("%d\n", ans.top());
}
}

本文作者 : NekoMio
知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
本文链接 : https://www.nekomio.com/2018/01/16/123/

本文最后更新于 天前,文中所描述的信息可能已发生改变