%%%
http://blog.csdn.net/qq_34454069/article/details/78757007
题目
Jiajia和Wind是一对恩爱的夫妻，并且他们有很多孩子。某天，Jiajia、Wind和孩子们决定在家里玩捉迷藏游戏。他们的家很大且构造很奇特，由N个屋子和N-1条双向走廊组成，这N-1条走廊的分布使得任意两个屋子都互相可达。
游戏是这样进行的，孩子们负责躲藏，Jiajia负责找，而Wind负责操纵这N个屋子的灯。在起初的时候，所有的灯都没有被打开。每一次，孩子们只会躲藏在没有开灯的房间中，但是为了增加刺激性，孩子们会要求打开某个房间的电灯或者关闭某个房间的电灯。为了评估某一次游戏的复杂性，Jiajia希望知道可能的最远的两个孩子的距离（即最远的两个关灯房间的距离）。
我们将以如下形式定义每一种操作：
C(hange) i 改变第i个房间的照明状态，若原来打开，则关闭；若原来关闭，则打开。
G(ame) 开始一次游戏，查询最远的两个关灯房间的距离。
一句话题意：给出一棵树，分为黑、白点，初始都是黑点，进行一些操作，改变点的颜色，询问最远的两个黑点
题解
动态点分治板题？？？
分治树和本树之间（搅过来搅过去）以至于调了好久。。。而且作死地把s1的下表滚动，也搅了一会儿
首先构建分治重心树
对于分治树上每个点i，维护两个堆
s1维护i的子树所有的黑点到i的父亲的值
（显然，最多只有n个子树）
s2维护i的每个儿子的s1的top
再储存一个ans，维护答案（即每个点s2最大值+次大值），答案即为ans的top
对于每个更新操作，就从该点对应的分治树上的点往上更新s1、s2、ans
然而怎么求距离呢
网上大部分都是用倍增rmq
其实呢，我们可以直接在构建重心树的时候就求出来节点i到它在分治树上祖先的距离
（来自某老阴比大佬的算法）
而且呢，由于只需要维护最大值，所以用两个优先队列代替multiset会好一些
（如果想知道怎么用优先队列，好像我不能提供什么帮助）
好像不止一些。。。
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#include<set>
#include<vector>
using namespace std;
#define itr multiset<int>::reverse_iterator
#define pp multiset<int>::iterator
const int N=100005,M=200005,P=100;
struct node{
int v,nxt;
}edge[M];
multiset<int>s1[N],s2[N],ans;
int dist[N][P],dcnt[N];
int id[N][P],pos;
int head[N],mcnt;
bool vis[N];
stack<int>S;
int fa[N][P];
int rt[N];
int cnt[N],sz[N];
bool ban[N];
bool light[N];
int n;
int lcnt;
void dfs(int u,int fat){
vis[u]=1;
cnt[u]=0;
sz[u]=1;
S.push(u);
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].v;
if(v==fat||ban[v])
continue ;
dfs(v,u);
sz[u]+=sz[v];
cnt[u]=max(cnt[u],sz[v]);
}
}
void find_dist(int u,int fat,int rt,int d,int idd){
dcnt[u]++;
dist[u][dcnt[u]]=d+1;
fa[u][dcnt[u]]=rt;
id[u][dcnt[u]]=idd;
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].v;
if(ban[v]||v==fat)
continue ;
find_dist(v,u,rt,d+1,idd);
}
}
int dfs1(int x,int rt){
memset(vis,0,sizeof vis);
dfs(x,-1);
int u=0,v=1<<30;
while(!S.empty()){
int y=S.top();
S.pop();
cnt[y]=max(cnt[y],sz[x]-sz[y]);
if(cnt[y]<v)
u=y,v=cnt[y];
}
return u;
}
void find_g(int u){
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].v;
if(ban[v])
continue ;
int x=dfs1(v,u);
if(!x)
continue ;
pos++;
find_dist(v,u,u,0,pos);
ban[x]=1;
find_g(x);
}
}
void add_edge(node a[],int u,int v){
mcnt++;
a[mcnt].v=v;
a[mcnt].nxt=head[u];
head[u]=mcnt;
}
void update1(int x){
itr it=s2[x].rbegin();
if(it==s2[x].rend())
return ;
else{
int maxx=*it;
it++;
if(it==s2[x].rend()){
if(light[x]){
pp del=ans.find(maxx);
if(del!=ans.end())
ans.erase(del);
}
}
else{
pp del=ans.find(maxx+(*it));
if(del!=ans.end())
ans.erase(del);
}
}
}
void update2(int x){
itr it=s2[x].rbegin();
if(it==s2[x].rend())
return ;
else{
int maxx=*it;
it++;
if(it==s2[x].rend()){
if(light[x])
ans.insert(maxx);
}
else{
ans.insert(maxx+(*it));
}
}
}
void turn_on(int x){
update1(x);
light[x]=1;
lcnt++;
update2(x);
for(int i=dcnt[x];i>=1;i--){
int idx=id[x][i],y=fa[x][i];
update1(y);
if(!s1[idx].empty()){
pp del=s2[y].find(*s1[idx].rbegin());
if(del!=s2[y].end())
s2[y].erase(del);
}
s1[idx].insert(dist[x][i]);
s2[y].insert(*s1[idx].rbegin());
update2(y);
}
}
void turn_off(int x){
update1(x);
light[x]=0;
lcnt--;
update2(x);
for(int i=dcnt[x];i>=1;i--){
int idx=id[x][i],y=fa[x][i];
update1(y);
pp del=s2[y].find(*s1[idx].rbegin());
if(del!=s2[y].end())
s2[y].erase(del);
del=s1[idx].find(dist[x][i]);
if(del!=s1[idx].end())
s1[idx].erase(del);
if(!s1[idx].empty())
s2[y].insert(*s1[idx].rbegin());
update2(y);
}
}
void init(){
scanf("%d",&n);
for(int i=1;i<=n-1;i++){
int u,v;
scanf("%d%d",&u,&v);
add_edge(edge,u,v);
add_edge(edge,v,u);
}
int x=dfs1(1,0);
ban[x]=1;
find_g(x);
for(int i=1;i<=n;i++){
turn_on(i);
}
}
void solve(){
int m;
scanf("%d\n",&m);
for(int i=1;i<=m;i++){
char c=getchar();
int a;
if(c=='G'){
if(lcnt==0)
printf("-1\n");
else if(lcnt==1)
printf("0\n");
else
printf("%d\n",*ans.rbegin());
}
else{
scanf("%d",&a);
if(light[a])
turn_off(a);
else
turn_on(a);
}
if(i!=m)
scanf("\n");
}
}
int main()
{
init();
solve();
}