idea1
可能会死掉的想法：考虑点分治维护每个分治中心x到达分治块内的个点距离，具体是用堆维护分治快内的x的儿子y到y的子树内的所有点距离（记为C[y]），取所有C[y]的top+e(x,y)放入x的堆里（记为B[x]），答案为所有B[x]的top+top2的最大值，可以在用一个堆维护（记为A）。
参考的实现，可以得到80分。
#include <queue>
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <iostream>
using namespace std;
const int N=1e5+10;
struct ErasableHeap {
std::priority_queue<int> A,B;
void insert(int w) {A.push(w);}
void erase(int w) {B.push(w);}
int size() {return A.size()-B.size();}
int top() {
while(B.size()&&A.top()==B.top()) A.pop(),B.pop();
return A.top();
}
int top2() {
int top1=top(); erase(top1);
int topt=top(); insert(top1);
return topt;
}
} A,B[N],C[N];
struct Edge {
int to,len,last;
} e[N<<1];
int n,q,val[N],tar[N];
int head[N];
void addEdge(int x,int y,int w) {
static int cnt=1;
e[++cnt]=(Edge){y,w,head[x]},head[x]=cnt;
e[++cnt]=(Edge){x,w,head[y]},head[y]=cnt;
}
namespace dbl {
int fa[N][20],ds[N][20],dep[N];
void pre(int x,int pa) {
dep[x]=dep[fa[x][0]=pa]+1;
for(int i=1; (1<<i)<=dep[x]; ++i) {
fa[x][i]=fa[fa[x][i-1]][i-1];
ds[x][i]=ds[x][i-1]+ds[fa[x][i-1]][i-1];
}
for(int i=head[x]; i; i=e[i].last) {
if(e[i].to==pa) continue;
ds[e[i].to][0]=e[i].len;
pre(e[i].to,x);
}
}
int getDis(int x,int y) {
if(dep[x]<dep[y]) std::swap(x,y);
int dif=dep[x]-dep[y],sum=0;
for(int i=19; ~i; --i)
if((dif>>i)&1) sum+=ds[x][i],x=fa[x][i];
if(x==y) return sum;
for(int i=19; ~i; --i) {
if(fa[x][i]!=fa[y][i]) {
sum+=ds[x][i],x=fa[x][i];
sum+=ds[y][i],y=fa[y][i];
}
}
return sum+ds[x][0]+ds[y][0];
}
}
void tryInsB(int x,int dis) {
if(B[x].size()==0) {
if(!val[x]) A.insert(dis);
B[x].insert(dis);
} else if(B[x].size()==1) {
if(!val[x]&&B[x].top()<dis) A.erase(B[x].top());
B[x].insert(dis);
A.insert(B[x].top()+B[x].top2());
} else if(B[x].top2()<dis) {
A.erase(B[x].top()+B[x].top2());
B[x].insert(dis);
A.insert(B[x].top()+B[x].top2());
} else B[x].insert(dis);
}
void tryEraB(int x,int dis) {
if(!B[x].size()) return; // notice
if(B[x].size()==1) {
if(!val[x]) A.erase(dis);
B[x].erase(dis);
} else if(B[x].top2()<=dis) {
A.erase(B[x].top()+B[x].top2());
B[x].erase(dis);
if(B[x].size()>1) A.insert(B[x].top()+B[x].top2());
else if(!val[x]) A.insert(B[x].top());
} else B[x].erase(dis);
}
int stk[N],top;
void whiteToBlack(int d) {
for(int i=tar[d]; i; i=tar[e[i^1].to]) stk[++top]=i;
for(int&i=top; i>=1; --i) {
int x=e[stk[i]^1].to;
int y=e[stk[i]].to,dis=dbl::getDis(d,y);
if(C[y].top()>dis) C[y].erase(dis);
else if(C[y].size()>1&&C[y].top2()==dis) C[y].erase(dis);
else {
tryEraB(x,dis+e[stk[i]].len); C[y].erase(dis);
if(C[y].size()) tryInsB(x,C[y].top()+e[stk[i]].len);
}
}
if(B[d].size()==1) A.erase(B[d].top());
val[d]=1;
}
void blackToWhite(int d) {
for(int i=tar[d]; i; i=tar[e[i^1].to]) stk[++top]=i;
for(int&i=top; i>=1; --i) {
int x=e[stk[i]^1].to;
int y=e[stk[i]].to,dis=dbl::getDis(d,y);
if(C[y].size()==0) C[y].insert(dis),tryInsB(x,dis+e[stk[i]].len);
else if(C[y].top()>=dis) C[y].insert(dis);
else {
tryEraB(x,C[y].top()+e[stk[i]].len); C[y].insert(dis);
tryInsB(x,dis+e[stk[i]].len);
}
}
if(B[d].size()==1) A.insert(B[d].top());
val[d]=0;
}
int rt,sum,siz[N];
bool ban[N];
void getRoot(int x,int fa) {
static int f[N]={N+N};
f[x]=0,siz[x]=1;
for(int i=head[x]; i; i=e[i].last) {
if(e[i].to==fa||ban[e[i].to]) continue;
getRoot(e[i].to,x);
siz[x]+=siz[e[i].to];
f[x]=std::max(f[x],siz[e[i].to]);
}
f[x]=std::max(f[x],sum-siz[x]);
if(f[x]<f[rt]) rt=x;
}
void getC(int x,int fa,int dis,int top) {
C[top].insert(dis);
for(int i=head[x]; i; i=e[i].last) {
if(e[i].to==fa||ban[e[i].to]) continue;
getC(e[i].to,x,dis+e[i].len,top);
}
}
void build(int x) {
ban[x]=true;
for(int i=head[x]; i; i=e[i].last) {
if(ban[e[i].to]) continue;
getC(e[i].to,x,0,e[i].to);
B[x].insert(C[e[i].to].top()+e[i].len);
}
for(int i=head[x]; i; i=e[i].last) {
if(ban[e[i].to]) continue;
rt=0;
sum=siz[e[i].to];
getRoot(e[i].to,x);
tar[rt]=i;
build(rt);
}
if(B[x].size()>1) A.insert(B[x].top()+B[x].top2());
else if(B[x].size()) A.insert(B[x].top());
}
int main() {
scanf("%d",&n);
for(int i=n,x,y; --i; ) {
scanf("%d%d",&x,&y);
addEdge(x,y,1);
}
dbl::pre(1,0);
sum=n;
getRoot(1,0);
build(rt);
int white=n,q,x;
char chr[5];
scanf("%d",&q);
while(q--) {
scanf("%s",chr);
if(*chr=='G') {
if(!white) puts("-1");
else if(white==1) puts("0");
else printf("%d
",std::max(0,A.top()));
} else {
scanf("%d",&x);
if(!val[x]) --white,whiteToBlack(x);
else ++white,blackToWhite(x);
}
}
return 0;
}
代码中的一个技巧：记录tar[x]表示上一级分治中心连向x所在子树的边的编号，这样就能在爬树时同时得到原树儿子(e[tar[i]].to)、边长(e[tar[i]].len)、和上一层的分治中心(e[tar[i]^1].to)。
但想法有一个缺陷：注意notice的那句，为什么会有这种情况出现？原来对于同一个y对应的x可能不唯一，且每种对应的意义不一样（因为对应x不同，分治块范围不同）。补救措施可以考虑建立分治树时将被对应多次的y拆开（拆开的点都对应原树上的‘y’节点），最坏情况下单点y会被拆成deg[y]个，但是处于极限状况的点个数不会太多，总点数仍是O(n)级别。
经过抢救的部分 90分弃坑了
int yCnt,yBel[N],myY[N],myX[N],myL[N];
void whiteToBlack(int d) {
for(int i=d; myX[i]; i=myX[i]) {
int x=myX[i];
int y=myY[i],dis=dbl::getDis(d,yBel[y]);
if(C[y].top()>dis) C[y].erase(dis);
else if(C[y].size()>1&&C[y].top2()==dis) C[y].erase(dis);
else {
tryEraB(x,dis+myL[i]); C[y].erase(dis);
if(C[y].size()) tryInsB(x,C[y].top()+myL[i]);
}
}
if(B[d].size()==1) A.erase(B[d].top());
val[d]=1;
}
void blackToWhite(int d) {
for(int i=d; myX[i]; i=myX[i]) {
int x=myX[i];
int y=myY[i],dis=dbl::getDis(d,yBel[y]);
if(C[y].size()==0) C[y].insert(dis),tryInsB(x,dis+myL[i]);
else if(C[y].top()>=dis) C[y].insert(dis);
else {
tryEraB(x,C[y].top()+myL[i]); C[y].insert(dis);
tryInsB(x,dis+myL[i]);
}
}
if(B[d].size()==1) A.insert(B[d].top());
val[d]=0;
}
int rt,sum,siz[N];
bool ban[N];
void getRoot(int x,int fa) {
static int f[N]={N+N};
f[x]=0,siz[x]=1;
for(int i=head[x]; i; i=e[i].last) {
if(e[i].to==fa||ban[e[i].to]) continue;
getRoot(e[i].to,x);
siz[x]+=siz[e[i].to];
f[x]=std::max(f[x],siz[e[i].to]);
}
f[x]=std::max(f[x],sum-siz[x]);
if(f[x]<f[rt]) rt=x;
}
void getC(int x,int fa,int dis,int top) {
C[top].insert(dis);
for(int i=head[x]; i; i=e[i].last) {
if(e[i].to==fa||ban[e[i].to]) continue;
getC(e[i].to,x,dis+e[i].len,top);
}
}
void build(int x) {
ban[x]=true;
for(int i=head[x]; i; i=e[i].last) {
if(ban[e[i].to]) continue;
yBel[++yCnt]=e[i].to;
getC(e[i].to,x,0,yCnt);
B[x].insert(C[yCnt].top()+e[i].len);
rt=0;
sum=siz[e[i].to];
getRoot(e[i].to,x);
myX[rt]=x;
myY[rt]=yCnt;
myL[rt]=e[i].len;
build(rt);
}
if(B[x].size()>1) A.insert(B[x].top()+B[x].top2());
else if(B[x].size()) A.insert(B[x].top());
}
idea2
别人的不会死掉的想法：直接用C[y]维护在x的分治块内y的子树中的所有节点到x的距离，B[x]取所有C[y]的最大值，由于不在依赖原树上的父子关系，避免了一个y对应了多个x的情况。
总结
我看别人题解的时候就不该看一半