题目描述
给出一棵边带权的节点数量为n的树，初始树上所有节点都是白色。有两种操作：
C x，改变节点x的颜色，即白变黑，黑变白
A，询问树中最远的两个白色节点的距离，这两个白色节点可以重合(此时距离为0)。
N (N <= 100000) Q <= 200000
时限1s
题解
如果没有修改的话，直接点分治，记录子树最深的白点即可。
但是有修改。
发现，点分治的递归层数是O(logn)的
而且这个递归的联通块的根形成一个树形结构。不妨叫点分树。
我们的答案是在所有递归出来的块里ans取max
发现，每次改变一个点的颜色，会影响自己的联通块，以及点分树上这个点的所有father的答案。
树高logn
所以，我们考虑暴力修改每一层的答案。
用三个堆来维护。
一个堆h0，维护这个点P所代表的点分树的联通块中所有点到点分树上P的father的距离（树上实际距离）。
（好处是，修改的时候，直接自底向上，父亲只要一个，这样不需要在上层再考虑哪个子树变了）
另一个堆h1，维护这个点P的所有儿子的堆顶的值。
我们从一个点P的h1堆里面，找到最大的和次大的，做和就是这一层的最大答案。
如果P是白点，那么答案可以只要最大的。而且ans最少是0
第三个堆，维护所有点代表的联通块的ans。最终答案就在这里。
然后，所有的修改，都是删除之后再插入。
堆的删除，用懒惰堆即可。
代码：
（实现细节较多：例如堆的empty判断）
（堆中不用记录答案出自哪里，随便删除一个，剩下那个就是没有删除的。是没有区别的。直接int的堆即可）
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define reg register int
#define il inline
#define numb (ch^'0')
using namespace std;
typedef long long ll;
il void rd(int &x){
char ch;x=;bool fl=false;
while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
for(x=numb;isdigit(ch=getchar());x=x*+numb);
(fl==true)&&(x=-x);
}
il void prin(int x){
if(x/) prin(x/);
putchar(x%+'');
}
namespace Miracle{
const int N=+;
const int inf=0x3f3f3f3f;
int n,m;
struct node{
int nxt,to;
int val;
}e[*N];
int hd[N],cnt;
il void add(int x,int y,int z){
e[++cnt].nxt=hd[x];
e[cnt].to=y;
e[cnt].val=z;
hd[x]=cnt;
}
int fa[N];
int sz[N];
int c[N];
priority_queue<int>h[][N],d[][N],hh,dd; int dis[N][];
int dep[N];
int nowsz;
int rt,mxsz[N];
int ans[N];
bool vis[N];
int gen;
il void dfs1(int x,int ff,int d){
dep[x]=d;
sz[x]=;
mxsz[x]=;
for(reg i=hd[x];i;i=e[i].nxt){
int y=e[i].to;
if(y==ff) continue;
if(vis[y]) continue;
dfs1(y,x,d);
sz[x]+=sz[y];
mxsz[x]=max(mxsz[x],sz[y]);
}
mxsz[x]=max(mxsz[x],nowsz-sz[x]);
if(mxsz[x]<=nowsz/){
rt=x;
}
}
il void dfs2(int x,int ff,int d){
sz[x]=;
if(d!=) h[][rt].push(dis[x][d-]);
for(reg i=hd[x];i;i=e[i].nxt){
int y=e[i].to;
if(vis[y]) continue;
if(y==ff) continue;
dis[y][d]=dis[x][d]+e[i].val;
dfs2(y,x,d);
sz[x]+=sz[y];
}
}
il void clear(int x,int k){
if(h[k][x].empty()) return;
while(d[k][x].size()&&h[k][x].size()&&h[k][x].top()==d[k][x].top()){
h[k][x].pop();d[k][x].pop();
}
}
il void upda(int x){
//cout<<" updaing "<<x<<endl;
ans[x]=-inf;
if(c[x]==) ans[x]=max(ans[x],);
clear(x,);
if(!h[][x].empty()){
//cout<<" sz "<<h[1][x].size()<<" "<<d[1][x].size()<<endl;
int tmp=h[][x].top();h[][x].pop();
//cout<<" tmp "<<tmp.id<<" "<<tmp.val<<endl;
if(c[x]==){
ans[x]=max(ans[x],tmp);
}
clear(x,);
if(!h[][x].empty()){
ans[x]=max(ans[x],tmp+(h[][x].top()));
}
h[][x].push(tmp);
}
}
il int divi(int x,int d,int ff){
//cout<<" x d ff "<<x<<" "<<d<<" "<<ff<<endl;
rt=;
dfs1(x,,d);
fa[rt]=ff;
dis[rt][d]=;
dfs2(rt,,d); vis[rt]=;
ans[rt]=-inf;
int now=rt;
for(reg i=hd[now];i;i=e[i].nxt){
int y=e[i].to;
if(vis[y]) continue;
nowsz=sz[y];
int son=divi(y,d+,now); if(h[][son].size()){
h[][now].push(h[][son].top());
}
}
upda(now);
//cout<<" rt "<<now<<" : "<<ans[now]<<endl;
hh.push(ans[now]);
return now;
}
il void wrk(int x){
int gg=x;
int nd=dep[x];
if(c[x]==){
c[x]^=;
while(x){
//cout<<" xx nd "<<x<<" "<<nd<<" "<<endl;
dd.push(ans[x]);
clear(x,);
upda(x);
hh.push(ans[x]); if(fa[x]){
if(h[][x].size()) d[][fa[x]].push(h[][x].top());
d[][x].push(dis[gg][nd-]);
clear(x,);
if(h[][x].size()) h[][fa[x]].push(h[][x].top());
} x=fa[x];
--nd;
}
}
else{
c[x]^=;
while(x){
dd.push(ans[x]);
clear(x,);
upda(x);
hh.push(ans[x]); if(fa[x]){
if(h[][x].size()) d[][fa[x]].push(h[][x].top());
h[][x].push(dis[gg][nd-]);
clear(x,);
if(h[][x].size()) h[][fa[x]].push(h[][x].top());
} x=fa[x];
--nd;
}
}
}
int main(){
scanf("%d",&n);int x,y,z;
for(reg i=;i<=n-;++i){
rd(x);rd(y);rd(z);
add(x,y,z);add(y,x,z);
}
nowsz=n;
gen=divi(,,);
int m;
rd(m);
char ch[];
while(m--){
scanf("%s",ch+);
if(ch[]=='A'){ while(dd.size()&&hh.size()&&hh.top()==dd.top()){
hh.pop();dd.pop();
}
if(!hh.size()){
puts("They have disappeared.");
}
else{
int tmp=hh.top();
if(tmp==-inf) puts("They have disappeared.");
else {
(tmp<)&&(tmp=-tmp,putchar('-'));
prin(tmp);putchar('\n');
}
}
}else{
rd(x);
wrk(x);
}
// cout<<" ans------- "<<endl;
// for(reg i=1;i<=n;++i){
// cout<<i<<" : "<<ans[i]<<endl;
// }
}
return ;
} }
int main(){
Miracle::main();
return ;
} /*
Author: *Miracle*
Date: 2018/11/28 9:20:15
*/
你也可以顺带AC[ZJOI2007]捉迷藏