原文链接https://www.cnblogs.com/zhouzhendong/p/BZOJ1095.html
题目传送门 - BZOJ1095
题意
有 N 个点，每一个点是黑色或者白色，一开始所有点的颜色都是黑色。有 M 次操作，每次操作有两种类型：1. 修改一个点的颜色；2. 查询树上所有黑色点对之间的距离最大值。
$Nleq 100000,mleq 500000$
题解
写个动态点分治。
对于一个点分中心，维护两个可删堆：
1. 维护一下当前连通块的所有黑点到 当前点分中心在点分树上的父亲节点 之间的距离。
2. 维护一下当前点分中心所有子树的最深深度，这个东西显然可以通过子树中维护的 1. 来得到。
对于全局，维护一个可删堆，把每一个节点的 2 号堆中最大两个值的和扔进去。
这个可删堆有一种方便的写法，见代码。
每次修改直接暴力上跳。注意堆中元素个数不足的情况。
求 LCA 最好写欧拉序 + 倍增。不然，虽然能在 BZOJ 通过，但是会在一个测试点 5s 的情况下被卡常。
代码
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
const int N=100005;
int read(){
int x=0;
char ch=getchar();
while (!isdigit(ch))
ch=getchar();
while (isdigit(ch))
x=(x<<1)+(x<<3)+ch-48,ch=getchar();
return x;
}
struct AB_Heap{
priority_queue <int> A,B;
int sz;
void clear(){
while (!A.empty())
A.pop();
while (!B.empty())
B.pop();
sz=0;
}
int size(){return sz;}
void push(int x){A.push(x),sz++;}
void pop(int x){B.push(x),sz--;}
int top(){
while (!B.empty()&&A.top()==B.top())
A.pop(),B.pop();
return A.top();
}
int top2(){
int x=top(),y;
pop(x),y=top(),push(x);
return x+y;
}
}S[N],SF[N],ans;
int n,m,tot;
int depth[N],in[N],out[N],eu[N*2],ST[N*2][20],Log[N*2];
int Dfa[N],vis[N],Time=0,size[N],Max[N],now[N];
vector <int> e[N];
void dfs1(int x,int pre,int d){
depth[x]=d,eu[in[x]=++Time]=x;
for (vector <int> :: iterator y=e[x].begin();y!=e[x].end();y++)
if ((*y)!=pre)
dfs1(*y,x,d+1),eu[++Time]=x;
out[x]=Time;
}
void Get_ST(int n){
Log[1]=0;
for (int i=2;i<=n;i++)
Log[i]=Log[i>>1]+1;
for (int i=1;i<=n;i++){
ST[i][0]=eu[i];
for (int j=1;j<20;j++){
ST[i][j]=ST[i][j-1];
int p=i-(1<<(j-1));
if (p>0&&depth[ST[p][j-1]]<depth[ST[i][j]])
ST[i][j]=ST[p][j-1];
}
}
}
int LCA(int x,int y){
if (in[x]>out[y])
swap(x,y);
int L=in[x],R=out[y],d=Log[R-L+1];
int a=ST[L+(1<<d)-1][d],b=ST[R][d];
return depth[a]<depth[b]?a:b;
}
int Distance(int x,int y){
return depth[x]+depth[y]-2*depth[LCA(x,y)];
}
int Node[N],Node_cnt=0;
void dfs2(int x,int pre){
if (vis[x]>=Time){
size[x]=0;
return;
}
size[x]=1,vis[x]=Time,Max[x]=0;
Node[++Node_cnt]=x;
for (vector <int> :: iterator y=e[x].begin();y!=e[x].end();y++){
if ((*y)==pre)
continue;
dfs2(*y,x);
size[x]+=size[*y];
Max[x]=max(Max[x],size[*y]);
}
}
int build(int x,int pre){
Time++,Node_cnt=0,dfs2(x,0);
int mi=x,v=Max[x];
for (int i=1;i<=Node_cnt;i++){
int y=Node[i],vy=max(Max[y],size[x]-size[y]);
if (vy<v)
v=vy,mi=y;
}
Dfa[x=mi]=pre,vis[x]=1e9,SF[x].clear();
for (int i=1;i<=Node_cnt;i++)
SF[x].push(Distance(pre,Node[i]));
S[x].clear(),S[x].push(0);
for (vector <int> :: iterator y=e[x].begin();y!=e[x].end();y++)
if (vis[*y]<1e9)
S[x].push(SF[build(*y,x)].top());
if (S[x].size()>=2)
ans.push(S[x].top2());
return x;
}
void update(int x){
if (S[x].size()>=2) ans.pop(S[x].top2());
if (now[x])
S[x].push(0);
else
S[x].pop(0);
if (S[x].size()>=2) ans.push(S[x].top2());
for (int y=x;Dfa[y];y=Dfa[y]){
int z=Dfa[y],d=Distance(x,z);
if (SF[y].size()&&SF[y].top()>d)
if (now[x])
SF[y].push(d);
else
SF[y].pop(d);
else {
if (S[z].size()>=2) ans.pop(S[z].top2());
if (SF[y].size()) S[z].pop(SF[y].top());
if (now[x])
SF[y].push(d);
else
SF[y].pop(d);
if (SF[y].size()) S[z].push(SF[y].top());
if (S[z].size()>=2) ans.push(S[z].top2());
}
}
tot+=now[x]?1:-1,now[x]^=1;
}
int main(){
tot=n=read();
for (int i=1;i<n;i++){
int a=read(),b=read();
e[a].push_back(b);
e[b].push_back(a);
}
dfs1(1,0,0),Get_ST(n*2-1);
ans.clear(),build(1,0);
m=read();
while (m--){
char ch[10];
scanf("%s",ch);
if (ch[0]=='C')
update(read());
else
printf("%d
",tot<=1?tot-1:ans.top());
}
return 0;
}