rockdu
题目描述
Jiajia和Wind是一对恩爱的夫妻，并且他们有很多孩子。某天，Jiajia、Wind和孩子们决定在家里玩捉迷藏游戏。他们的家很大且构造很奇特，由N个屋子和N-1条双向走廊组成，这N-1条走廊的分布使得任意两个屋子都互相可达。
游戏是这样进行的，孩子们负责躲藏，Jiajia负责找，而Wind负责操纵这N个屋子的灯。在起初的时候，所有的灯都没有被打开。每一次，孩子们只会躲藏在没有开灯的房间中，但是为了增加刺激性，孩子们会要求打开某个房间的电灯或者关闭某个房间的电灯。为了评估某一次游戏的复杂性，Jiajia希望知道可能的最远的两个孩子的距离（即最远的两个关灯房间的距离）。
我们将以如下形式定义每一种操作：
- C(hange) i 改变第i个房间的照明状态，若原来打开，则关闭；若原来关闭，则打开。
- G(ame) 开始一次游戏，查询最远的两个关灯房间的距离。
输入输出格式
输入格式：
第一行包含一个整数N，表示房间的个数，房间将被编号为1,2,3…N的整数。
接下来N-1行每行两个整数a, b，表示房间a与房间b之间有一条走廊相连。
接下来一行包含一个整数Q，表示操作次数。接着Q行，每行一个操作，如上文所示。
输出格式：
对于每一个操作Game，输出一个非负整数到hide.out，表示最远的两个关灯房间的距离。若只有一个房间是关着灯的，输出0；若所有房间的灯都开着，输出-1。
输入输出样例
说明
对于20%的数据， N ≤50, M ≤100；
对于60%的数据， N ≤3000, M ≤10000； 对于100%的数据， N ≤100000, M ≤500000。
可以说是点分树的模板题目了。首先对于只有一个询问的情况我们可以暴力bfs解决，那么既然要带修改的话自然考虑点分树：把点分治每一层建立成树形结构。对每一块分治维护：1、当前分治的子树下，以连向上一层的点为根向下最深关灯房间的深度。2、当前重心下，把每一个子树的最深关灯房间拿出来，其中深度值的最大值和次大值。（一个是不能在同一个子树，因为必须经过重心。另外如果当前重心为关灯的房间的话，那么0也是一个合法的值）。并且要支持修改。那么我们就开两个map，分别对重心维护以上的两个值。每有一个修改就沿着点分树跳到根，一边跳一边更新两个信息，并且更改当前重心统计的答案。最后再用一个map来维护所有重心统计答案的最大值就好了。
但是map常数太大了，有没有有没一点的写法呢？
答案是有的，我们可以写一个可删除的堆！具体做法是对于一个可删除堆，我们用两个堆维护，一个记录删除的键值，一个记录插入的键值。每有一个插入我们把它加到插入堆，每有一个删除我们把它加到删除堆。这样之后，只需要再top()和pop()时，把两个堆堆顶相同的部分先全部弹掉再操作就好了。因为删除最多删除插入的那么多个，所以总复杂度还是O(n log n)的，而且常数和map相比非常小。
// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;
struct edge {
int v, next;
}e[maxn << 1];
int head[maxn], cnt, tot, ans;
void adde(const int &u, const int &v) {
e[++cnt] = (edge) {v, head[u]};
head[u] = cnt;
}
struct Heap {
priority_queue<int > M, D;
void push(int x) {M.push(x);}
void del(int x) {D.push(x);}
void pop() {
while(!M.empty() && !D.empty() && M.top() == D.top())
M.pop(), D.pop();
M.pop();
}
int top() {
while(!M.empty() && !D.empty() && M.top() == D.top())
M.pop(), D.pop();
return M.empty() ? -1 : M.top();
}
int Qms() {
int mx1 = top(), mx2, ans;
if(!(~mx1)) return 0;
pop(), mx2 = top();
if(!(~mx2)) return push(mx1), 0;
return push(mx1), mx1 + mx2;
}
} Ans[maxn], Nd[maxn], All;
int size[maxn], mx[maxn], G, vis[maxn];
void FG(int u, int f, int & G, int tot) {
size[u] = 1, mx[u] = 0;
for(register int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if(vis[v] || v == f) continue;
FG(v, u, G, tot), size[u] += size[v];
mx[u] = max(mx[u], size[v]);
}
mx[u] = max(mx[u], tot - size[u]);
if(mx[u] < mx[G]) G = u;
}
int LG[maxn], fa[maxn], lyr[maxn], Dp[maxn][22], Tp[maxn], Ap[maxn];
void GetInit(int u, int f, int G, int L, int w) {
size[u] = 1;
Dp[u][L] = w, Nd[G].push(w);
for(register int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if(vis[v] || v == f) continue;
GetInit(v, u, G, L, w + 1);
size[u] += size[v];
}
}
void solve(int u, int rt, int L) {
int v, tmp;
GetInit(rt, 0, u, L, 1), vis[u] = 1, lyr[u] = L;
for(register int i = head[u]; i; i = e[i].next) {
v = e[i].v;
if(vis[v]) continue;
G = 0, FG(v, 0, G, size[v]), tmp = G;
fa[G] = u, solve(G, v, L + 1);
Tp[tmp] = Nd[tmp].top();
Ans[u].push(Tp[tmp]);
}
Ans[u].push(0);
All.push(Ap[u] = Ans[u].Qms());
}
void CG(int u) {
if(!LG[u]) ++tot, LG[u] = 1, Ans[u].del(0);
else --tot, LG[u] = 0, Ans[u].push(0);
int tmp, p = u, as = Ans[u].Qms(), fp = fa[p];
if(Ap[u] != as) All.push(as), All.del(Ap[u]), Ap[u] = as;
while(fp) {
if(!LG[u]) Nd[p].push(Dp[u][lyr[p]]);
else Nd[p].del(Dp[u][lyr[p]]);
tmp = Nd[p].top();
if(Tp[p] != tmp) {
if(~Tp[p]) {Ans[fp].del(Tp[p]);}
if(~tmp) {Ans[fp].push(tmp);}
Tp[p] = tmp;
}
as = Ans[fp].Qms();
if(Ap[fp] != as)
All.push(as), All.del(Ap[fp]), Ap[fp] = as;
p = fa[p], fp = fa[p];
}
}
char s[3];
int n, m, u, v, root;
int main() {
mx[0] = inf;
scanf("%d", &n);
for(register int i = 1; i < n; ++i)
scanf("%d%d", &u, &v), adde(u, v), adde(v, u);
G = 0, FG(1, 0, G, n), root = G;
solve(G, 1, 0);
scanf("%d", &m);
for(register int i = 1; i <= m; ++i) {
scanf("%s", s);
if(s[0] == 'G') printf("%d\n", All.top());
else scanf("%d", &u), CG(u);
}
return 0;
}
没有帐号? 立即注册