BZOJ1095 [ZJOI2007] Hide 捉迷藏

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#

Sample Output#

HINT#

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

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

ans 维护答案

1
#pragma GCC optimize("O3")
2
#include <cstdio>
3
#include <cstring>
4
#include <algorithm>
5
#include <queue>
6
#include <iostream>
7
#include<ext/pb_ds/priority_queue.hpp>
8
using namespace std;
9
inline int read()
10
{
11
    int x=0,f=1;char ch=getchar();
12
    while(ch<'0'||ch>'9'){if(ch=='0')f=-1;ch=getchar();}
13
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
14
    return x*f;
15
}
16
const int MAXN = 100005;
17
struct Priority_queue
18
{
19
    __gnu_pbds::priority_queue<int, less<int>, __gnu_pbds::binary_heap_tag> Q1, Q2;
20
    inline int size()
21
    {
22
        return Q1.size() - Q2.size();
23
    }
24
    inline void push(const int &x)
25
    {
26
        Q1.push(x);
27
    }
28
    inline void erase(const int &x)
29
    {
30
        Q2.push(x);
31
    }
32
    inline int top()
33
    {
34
        while (!Q2.empty() && Q1.top() == Q2.top())
35
        {
36
            Q1.pop();
37
            Q2.pop();
38
        }
39
        if (!Q1.empty()) return Q1.top();
40
        else return 0;
41
    }
42
    inline int top2()
43
    {
44
        if (size() < 2) return 0;
45
        while (!Q2.empty() && Q1.top() == Q2.top())
46
        {
47
            Q1.pop();
48
            Q2.pop();
49
        }
50
        int tmp = Q1.top(); Q1.pop();
51
        while (!Q2.empty() && Q1.top() == Q2.top())
52
        {
53
            Q1.pop();
54
            Q2.pop();
55
        }
56
        int ans = Q1.top(); Q1.push(tmp);
57
        return ans;
58
    }
59
}B[MAXN], C[MAXN], ans;
60
struct edge
61
{
62
    int END, next;
63
}v[MAXN << 1];
64
int first[MAXN], p;
65
inline void add(int a, int b)
66
{
67
    v[p].END = b;
68
    v[p].next = first[a];
69
    first[a] = p++;
70
}
71
int f[MAXN][18];
72
int dep[MAXN];
73
inline void PreDFS(int rt, int fa)
74
{
75
    dep[rt] = dep[fa] + 1;
76
    f[rt][0] = fa;
77
    for (int i = 1; i <= 17; i++) f[rt][i] = f[f[rt][i - 1]][i - 1];
78
    for (int i = first[rt]; i != -1; i = v[i].next)
79
    {
80
        if (v[i].END == fa) continue;
81
        PreDFS(v[i].END, rt);
82
    }
83
}
84
int sum, Max[MAXN], size[MAXN], root;
85
bool vis[MAXN];
86
static inline void GetRoot(int rt, int fa)
87
{
88
    size[rt] = 1; Max[rt] = 0;
89
    for (int i = first[rt]; i != -1; i = v[i].next)
90
    {
91
        if (vis[v[i].END] || v[i].END == fa) continue;
92
        GetRoot(v[i].END, rt);
93
        size[rt] += size[v[i].END];
94
        Max[rt] = max(Max[rt], size[v[i].END]);
95
    }
96
    Max[rt] = max(Max[rt], sum - size[rt]);
97
    if (Max[rt] < Max[root]) root = rt;
98
}
99
int Fa[MAXN];
100
static inline void Divide(int rt, int fa)
101
{
102
    vis[rt] = 1;
103
    Fa[rt] = fa;
104
    // cerr << rt << endl;
105
    for (int i = first[rt]; i != -1; i = v[i].next)
106
    {
107
        if (vis[v[i].END]) continue;
108
        sum = size[v[i].END], root = 0;
109
        GetRoot(v[i].END, 0);
110
        Divide(root, rt);
111
    }
112
}
113
static inline int LCA(int a, int b)
114
{
115
    if (dep[a] < dep[b]) swap(a, b);
116
    int d = dep[a] - dep[b];
117
    for (int i = 17; i >= 0; i--)
118
        if (d & (1 << i))
119
            d -= (1 << i), a = f[a][i];
120
    if (a == b) return a;
121
    for (int i = 17; i >= 0; i--)
122
        if (f[a][i] != f[b][i])
123
            a = f[a][i], b = f[b][i];
124
    return f[a][0];
125
}
126
static inline int dis(const int &a, const int &b)
127
{
128
    return dep[a] + dep[b] - 2 * dep[LCA(a, b)];
129
}
130
int Color[MAXN];
131
static inline void Change_To_Black(const int &Height_root, const int &Child)
132
{
133
    if (Height_root == Child)
134
    {
135
        B[Height_root].push(0);
136
        if (B[Height_root].size() == 2)
137
            ans.push(B[Height_root].top());
138
    }
139
    if (!Fa[Height_root]) return;
140
    int Father = Fa[Height_root];
141
    int Dis = dis(Father, Child);
142
    int tmp = C[Height_root].top();
143
    C[Height_root].push(Dis);
144
    if (Dis > tmp)
145
    {
146
        int size = B[Father].size();
147
        int tmp2 = B[Father].top() + B[Father].top2();
148
        if (tmp)
149
            B[Father].erase(tmp);
150
        B[Father].push(Dis);
151
        int now = B[Father].top() + B[Father].top2();
152
        if (now > tmp2)
153
        {
154
            if (size >= 2) ans.erase(tmp2);
155
            if (B[Father].size() >= 2)
156
                ans.push(now);
157
        }
158
    }
159
    Change_To_Black(Father, Child);
160
}
161
static inline void Change_To_White(const int &Height_root, const int &Child)
162
{
163
    if (Height_root == Child)
164
    {
165
        if (B[Height_root].size() == 2)
166
            ans.erase(B[Height_root].top());
167
        B[Height_root].erase(0);
168
    }
169
    if (!Fa[Height_root]) return;
170
    int Father = Fa[Height_root];
171
    int Dis = dis(Father, Child);
172
    int tmp = C[Height_root].top();
173
    C[Height_root].erase(Dis);
174
    if (tmp == Dis)
175
    {
176
        int size = B[Father].size();
177
        int tmp2 = B[Father].top() + B[Father].top2();
178
        B[Father].erase(Dis);
179
        if (C[Height_root].top())
180
            B[Father].push(C[Height_root].top());
181
        int now = B[Father].top() + B[Father].top2();
182
        if (now < tmp2)
183
        {
184
            if (size >= 2)
185
                ans.erase(tmp2);
186
            if (B[Father].size() >= 2)
187
                ans.push(now);
188
        }
189
    }
190
    Change_To_White(Father, Child);
191
}
192
int main()
193
{
194
    memset (first, -1, sizeof (first));
195
    int n = read();
196
    for (int i = 1; i < n; i++)
197
    {
198
        int a = read(), b = read();
199
        add(a, b);
200
        add(b, a);
201
        // cerr << i << endl;
202
    }
203
    PreDFS(1, 0);
204

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

208
    Divide(root, 0);
209
    // cerr << "11!!" << endl;
210
    for (int i = 1; i <= n; i++)
211
    {
212
        Color[i] = 1;
213
        // cerr << i << endl;
214
        C[i].push(0);
215
        // Change_To_Black(i, i);
216
    }
217
    for (int i = 1; i <= n; i++)
218
    {
219
        Change_To_Black(i, i);
220
        // cerr << i << endl;
221
    }
222
    // for (int i = 1; i <= n; i++) cerr << "i fa is " << Fa[i] << endl;
223
    int m = read();
224
    char s[10];
225
    for (int i = 1; i <= m; i++)
226
    {
227
        // cerr << i << endl;
228
        scanf ("%s", s);
229
        if (s[0] == 'C')
230
        {
231
            int k = read();
232
            if (Color[k])
233
            {
234
                Color[k] = 0;
235
                Change_To_White(k, k);
236
            }
237
            else
238
            {
239
                Color[k] = 1;
240
                Change_To_Black(k, k);
241
            }
242
        }
243
        else
244
            printf ("%d\n", ans.top());
245
    }
246
}