动态点分治，建出点分树。每个点维护每个子树黑点到其的距离$max$的一个堆，那么怎么维护呢，对于他的儿子，要维护其子树所有黑点到其父亲的距离的堆，然后$maintain$就可以了。最后再维护一个全局答案的堆就好了。
修改的时候真恶心。
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<cmath> 6 #include<queue> 7 #define N 100005 8 using namespace std; 9 struct heap{ 10 priority_queue<int> a,b; 11 void push(int x){a.push(x);} 12 void erase(int x){b.push(x);} 13 void update(){ 14 while(b.size()&&a.top()==b.top()) 15 a.pop(),b.pop(); 16 } 17 void pop(){update();a.pop();} 18 int top(){update();return a.top();} 19 int sec(){ 20 int x=top();pop(); 21 int y=top();push(x); 22 return y; 23 } 24 int size(){return a.size()-b.size();} 25 }A[N],B[N],C;//A:子树到父亲 B:max(son->A) C:max(B) 26 int e=1,head[N]; 27 struct edge{int v,next;}ed[N<<1]; 28 void add(int u,int v){ed[e].v=v;ed[e].next=head[u];head[u]=e++;} 29 int dep[N],fa[N][20]; 30 void dfs(int x,int d){ 31 dep[x]=d; 32 for(int i=1;(1<<i)<=d;i++) 33 fa[x][i]=fa[fa[x][i-1]][i-1]; 34 for(int i=head[x];i;i=ed[i].next){ 35 int v=ed[i].v; 36 if(v==fa[x][0])continue; 37 fa[v][0]=x;dfs(v,d+1); 38 } 39 } 40 int lca(int x,int y){ 41 if(dep[x]<dep[y])swap(x,y); 42 for(int i=17;~i;i--) 43 if(dep[fa[x][i]]>=dep[y])x=fa[x][i]; 44 if(x==y)return x; 45 for(int i=17;~i;i--) 46 if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i]; 47 return fa[x][0]; 48 } 49 int dis(int x,int y){ 50 return dep[x]+dep[y]-2*dep[lca(x,y)]; 51 } 52 int size[N],maxn[N],f[N]; 53 bool vis[N]; 54 int n,m,root,sum; 55 void getroot(int x,int fa){ 56 size[x]=1;maxn[x]=0; 57 for(int i=head[x];i;i=ed[i].next){ 58 int v=ed[i].v; 59 if(v==fa||vis[v])continue; 60 getroot(v,x); 61 size[x]+=size[v]; 62 maxn[x]=max(maxn[x],size[v]); 63 } 64 maxn[x]=max(maxn[x],sum-size[x]); 65 if(maxn[x]<maxn[root])root=x; 66 } 67 void init(int x){ 68 vis[x]=1; 69 int all=sum; 70 for(int i=head[x];i;i=ed[i].next){ 71 int v=ed[i].v; 72 if(vis[v])continue; 73 sum=size[v]<size[x]?size[v]:all-size[x]; 74 root=0;getroot(v,0); 75 f[root]=x; 76 init(root); 77 } 78 } 79 void build(){ 80 for(int i=1;i<=n;i++){ 81 int now=i; 82 while(f[now]){ 83 A[now].push(dis(i,f[now])); 84 now=f[now]; 85 } 86 } 87 for(int i=1;i<=n;i++) 88 if(f[i])B[f[i]].push(A[i].top()); 89 for(int i=1;i<=n;i++) 90 if(B[i].size()>=2)C.push(B[i].top()+B[i].sec()); 91 } 92 int col[N]; 93 void out(int now,int maxn){ 94 if(B[f[now]].size()<=2){ 95 B[f[now]].erase(maxn); 96 if(B[f[now]].size()==1)C.erase(B[f[now]].top()+maxn); 97 } 98 else{ 99 C.erase(B[f[now]].top()+B[f[now]].sec()); 100 B[f[now]].erase(maxn); 101 C.push(B[f[now]].top()+B[f[now]].sec()); 102 } 103 } 104 void in(int now){ 105 if(B[f[now]].size()<2){ 106 B[f[now]].push(A[now].top()); 107 if(B[f[now]].size()==2)C.push(B[f[now]].top()+B[f[now]].sec()); 108 } 109 else{ 110 int old=B[f[now]].top()+B[f[now]].sec();C.erase(old); 111 B[f[now]].push(A[now].top());C.push(B[f[now]].top()+B[f[now]].sec()); 112 } 113 } 114 void change(int x){ 115 if(col[x]){ 116 int now=x; 117 while(f[now]){ 118 if(!A[now].size()){ 119 A[now].push(dis(x,f[now])); 120 in(now); 121 } 122 else{ 123 int maxn=A[now].top(); 124 A[now].push(dis(x,f[now])); 125 if(maxn!=A[now].top())out(now,maxn),in(now); 126 } 127 now=f[now]; 128 } 129 } 130 else{ 131 int now=x; 132 while(f[now]){ 133 int d=dis(x,f[now]); 134 if(d==A[now].top()){ 135 A[now].erase(d);out(now,d); 136 if(A[now].size())in(now); 137 } 138 else A[now].erase(d); 139 now=f[now]; 140 } 141 } 142 col[x]^=1; 143 } 144 int main(){ 145 scanf("%d",&n); 146 for(int i=1,u,v;i<n;i++){ 147 scanf("%d%d",&u,&v); 148 add(u,v);add(v,u); 149 } 150 root=0;maxn[0]=N;sum=n; 151 dfs(1,1); 152 getroot(1,0); 153 init(root); 154 build();sum=n; 155 scanf("%d",&m); 156 char ch[2];int x; 157 while(m--){ 158 scanf("%s",ch); 159 if(ch[0]=='G'){ 160 if(sum<2)printf("%d ",sum-1); 161 else printf("%d ",C.top()); 162 } 163 else{ 164 scanf("%d",&x); 165 change(x); 166 if(col[x])sum--; 167 else sum++; 168 } 169 } 170 }