「BZOJ1095」[ZJOI2007]Hide 捉迷藏

Description

iajia和Wind是一对恩爱的夫妻,并且他们有很多孩子。某天,Jiajia、Wind和孩子们决定在家里玩捉迷藏游戏。他们的家很大且构造很奇特,由NN个屋子和N1N-1条双向走廊组成,这N1N-1条走廊的分布使得任意两个屋子都互相可达。

游戏是这样进行的,孩子们负责躲藏,Jiajia负责找,而Wind负责操纵这N个屋子的灯。在起初的时候,所有的灯都没有被打开。每一次,孩子们只会躲藏在没有开灯的房间中,但是为了增加刺激性,孩子们会要求打开某个房间的电灯或者关闭某个房间的电灯。为了评估某一次游戏的复杂性,Jiajia希望知道可能的最远的两个孩子的距离(即最远的两个关灯房间的距离)。

我们将以如下形式定义每一种操作:

  • C(hange) i 改变第i个房间的照明状态,若原来打开,则关闭;若原来关闭,则打开。
  • G(ame) 开始一次游戏,查询最远的两个关灯房间的距离。

Input

第一行包含一个整数N,表示房间的个数,房间将被编号为1,2,3N1,2,3\cdots N的整数。

接下来N1N-1行每行两个整数aa, bb,表示房间aa与房间bb之间有一条走廊相连。

接下来一行包含一个整数QQ,表示操作次数。接着QQ行,每行一个操作,如上文所示。

Output

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

对于20%20\%的数据, N50,M100N \leq 50, M \leq 100
对于60%60\%的数据, N3000,M10000N \leq 3000, M \leq 10000
对于100%100\%的数据, N100000,M500000N \leq 100000, M \leq 500000

Solution

动态点分治的板子题。、
每个点维护两个堆,然后全局维护一个答案堆
AxA_x表示所有黑点到xx的父亲FF的距离集合
BxB_x表示所有黑点到xx的距离集合。
显然BxB_x的大小=1=1的时候,必须取这个点,否则要么就是从子树到xx或者从子树到xx再到另一棵子树。
BxB_x由不同子树地AxA_x集合最大值构成。

全局堆是所有xxBB堆的第二大和第一大相加的集合。

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#include<queue>
#include<cassert>
#include<set>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 310000, M = 310000;
struct Edge {
int u, v, nxt;
}e[M];
int n, m, en, head[N];
void addedge(int x, int y) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en;
}
int num;
int L[N], R[N], b[N], d[N], siz[N];
void dfs(int x, int F) {
L[x] = ++num;
b[num] = x;
d[x] = d[F] + 1;
siz[x] = 1;
for(int i = head[x]; i;i = e[i].nxt) {
int y = e[i].v;
if(y == F) continue;
dfs(y, x);
siz[x] += siz[y];
b[++num] = x;
}
R[x] = num;
}
int g[N][21];
void init() {
for(int i = 1; i <= num; ++i) g[i][0] = b[i];
for(int i = 1; i <= 20; ++i)
for(int j = 1; j + (1 << i) - 1 <= num; ++j) {
if(d[g[j][i - 1]] < d[g[j + (1 << i - 1)][i - 1]]) g[j][i] = g[j][i - 1];
else g[j][i] = g[j + (1 << i - 1)][i - 1];
}
}
int lg[N];
int lca(int x, int y) {
x = L[x];
y = L[y];
if(x > y) swap(x, y);
int t = lg[y - x + 1];
if(d[g[x][t]] < d[g[y - (1 << t) + 1][t]]) return g[x][t];
return g[y - (1 << t) + 1][t];
}
int getdis(int x, int y) {
int z = lca(x, y);
return d[x] + d[y] - 2 * d[z];
}
struct Hep {
priority_queue<int>q, del;
void insert(int x) {q.push(x);}
void erase(int x) {del.push(x);}
void pop() {while(!del.empty() && q.top() == del.top()) q.pop(),del.pop(); q.pop();}
int top() {
while(!del.empty() && q.top() == del.top()) q.pop(),del.pop();
return q.top();
}
int ttop() {
while(!del.empty() && q.top() == del.top()) q.pop(),del.pop();
int x = q.top();
q.pop();
while(!del.empty() && q.top() == del.top()) q.pop(),del.pop(); //注意別漏了
int y = q.top();
q.push(x);
return y;
}
int size() {
return q.size() - del.size();
}
}A[N], B[N], C;
/*
A[x]: 存儲 到fa[x]的所有距離
B[x]: 存儲到x的距離
C: 存儲答案
*/
void ins(Hep &x) {
if(x.size() < 2) return;
int X = x.top();
int Y = x.ttop();
C.insert(X + Y);
}
void Del(Hep &x) {
if(x.size() < 2) return;
int X = x.top();
int Y = x.ttop();
C.erase(X + Y);
}
int sum, mx[N];
bool vis[N];
void Find(int x, int F, int &rt) {
siz[x] = 1;
mx[x] = 0;
for(int i = head[x]; i;i = e[i].nxt) {
int y = e[i].v;
if(y == F || vis[y]) continue;
Find(y, x, rt);
siz[x] += siz[y];
mx[x] = max(mx[x], siz[y]);
}
mx[x] = max(mx[x], sum - mx[x]);
if(mx[x] < mx[rt]) rt = x;
}
void cal(int x, int F, int dep, Hep & v) {
v.insert(dep);
for(int i = head[x]; i;i = e[i].nxt) if(!vis[e[i].v] && e[i].v != F) cal(e[i].v, x, dep + 1, v);
}
int fa[N];
int solve(int x, int F) {
sum = siz[x];
int rt = 0;
Find(x, 0, rt);
x = rt;
vis[x] = 1;
B[x].insert(0);
for(int i = head[x]; i;i = e[i].nxt) {
int y = e[i].v;
if(vis[y]) continue;
Hep s;
cal(y, 0, 1, s);
int z = solve(y, x);
A[z] = s;
fa[z] = x;
B[x].insert(A[z].top());
}
ins(B[x]);
return x;
}
int a[N];
void update(int x, int F) {
Del(B[x]);
if(F) B[x].erase(0);
else B[x].insert(0);
ins(B[x]);
for(int i = x, y; y = fa[i]; i = fa[i]) {
Del(B[y]);
if(A[i].size())B[y].erase(A[i].top());
if(F)
A[i].erase(getdis(y, x));
else A[i].insert(getdis(y, x));
if(A[i].size())B[y].insert(A[i].top());
ins(B[y]);
}
}

char op[5];
int main() {
freopen("1095.in","r",stdin);
freopen("1095.out","w",stdout);
n = read();
for(int i = 1; i < n; ++i) {
int x = read(), y = read();
addedge(x, y);
addedge(y, x);
}
dfs(1, 0);
init();
m = read();
C.insert(0);
for(int i = 2; i<= num; ++i) lg[i] = lg[i>>1]+1;
mx[0] = 1e9;
solve(1, 0);
for(int T = 1; T <= m; ++T) {
scanf("%s", op);
if(op[0] == 'C') {
int x = read();
a[x] ^= 1;
update(x, a[x]);
} else writeln(C.top());
}
return 0;
}