Description 捉迷藏
Jiajia和Wind是一对恩爱的夫妻，并且他们有很多孩子。某天，Jiajia、Wind和孩子们决定在家里玩
捉迷藏游戏。他们的家很大且构造很奇特，由N个屋子和N-1条双向走廊组成，这N-1条走廊的分布使得任意两个屋
子都互相可达。游戏是这样进行的，孩子们负责躲藏，Jiajia负责找，而Wind负责操纵这N个屋子的灯。在起初的
时候，所有的灯都没有被打开。每一次，孩子们只会躲藏在没有开灯的房间中，但是为了增加刺激性，孩子们会要
求打开某个房间的电灯或者关闭某个房间的电灯。为了评估某一次游戏的复杂性，Jiajia希望知道可能的最远的两
个孩子的距离（即最远的两个关灯房间的距离）。 我们将以如下形式定义每一种操作： C(hange) i 改变第i个房
间的照明状态，若原来打开，则关闭；若原来关闭，则打开。 G(ame) 开始一次游戏，查询最远的两个关灯房间的 距离。 Input
第一行包含一个整数N，表示房间的个数，房间将被编号为1,2,3…N的整数。接下来N-1行每行两个整数a, b，
表示房间a与房间b之间有一条走廊相连。接下来一行包含一个整数Q，表示操作次数。接着Q行，每行一个操作，如 上文所示。 Output
对于每一个操作Game，输出一个非负整数到hide.out，表示最远的两个关灯房间的距离。若只有一个房间是关
着灯的，输出0；若所有房间的灯都开着，输出-1。
边分治模板题，SPOJ上的卡不过去。
动态点分治做法见【这里】。
每次选择一条边，左右两边分别用一个堆来维护到这条边的最远距离。因为不想手写堆，所以自创了删点以后加到map里的方法。反正复杂度不会变坏。
#include<cstdio>
#include<cstring>
#include<map>
#include<queue>
#include<ctime>
#include<vector>
#include<algorithm>
using namespace std;
const int oo=0x3f3f3f3f;
vector<int> t1[1000010];
int tem[1000010];
priority_queue<pair<int,int> > pq[1000010];
map<int,int> mp[1000010];
int fir[1000010],ne[1000010],to[1000010],w[1000010],val[1000010],du[1000010],
clr[1000010],vis[1000010],del[1000010],size[1000010],ls[1000010],rs[1000010],
pos[1000010],fa[1000010],
n,root,low,R,num,clo;
int rd()
{int x=0;char c=getchar();while (c<'0'||c>'9') c=getchar();while (c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x;
}
char rdc()
{char c=getchar();while (c<'A'||c>'Z') c=getchar();return c;
}
void add(int u,int v,int x)
{num++;ne[num*2]=fir[u];fir[u]=num*2;to[num*2]=v;w[num*2]=x;ne[num*2+1]=fir[v];fir[v]=num*2+1;to[num*2+1]=u;w[num*2+1]=x;
}
void dfs2(int u,int fa,int siz)
{int v;size[u]=1;for (int i=fir[u];i;i=ne[i])if (!del[i>>1]&&!vis[i>>1]&&(v=to[i])!=fa){dfs2(v,u,siz);size[u]+=size[v];if (root==-1||max(size[v],siz-size[v])<max(size[root],siz-size[root]))root=i>>1,low=v;}
}
void dfs3(int u,int fa,int dis,int with)
{int v;pq[with].push(make_pair(dis,u));for (int i=fir[u];i;i=ne[i])if (!del[i>>1]&&!vis[i>>1]&&(v=to[i])!=fa)dfs3(v,u,dis+w[i],with);
}
void up(int u)
{pair<int,int> p1,p2;p1.second=p2.second=-1;while (!pq[ls[u]].empty()){p1=pq[ls[u]].top();if (clr[p1.second]){pq[ls[u]].pop();mp[ls[u]][p1.second]=p1.first;p1.second=-1;}else break;}while (!pq[rs[u]].empty()){p2=pq[rs[u]].top();if (clr[p2.second]){pq[rs[u]].pop();mp[rs[u]][p2.second]=p2.first;p2.second=-1;}else break;}val[u]=max(val[ls[u]],val[rs[u]]);if (p1.second!=-1&&p2.second!=-1) val[u]=max(val[u],p1.first+p2.first+w[u<<1]);
}
int dfs1(int u,int siz)
{if (siz==1){pos[u]=++clo;pq[clo].push(make_pair(0,u));if (clr[u]) val[clo]=-oo;else val[clo]=0;return clo;}int r1,x,y,sx,sy;root=-1;dfs2(u,-1,siz);vis[r1=root]=1;x=to[r1<<1];y=to[r1<<1|1];if (x==low) sx=size[x],sy=siz-size[x];else sx=siz-size[y],sy=size[y];ls[r1]=dfs1(x,sx);fa[ls[r1]]=r1;rs[r1]=dfs1(y,sy);fa[rs[r1]]=r1;dfs3(x,-1,0,ls[r1]);dfs3(y,-1,0,rs[r1]);up(r1);vis[r1]=0;return r1;
}
void modi(int u)
{int p=pos[u];clr[u]^=1;if (!clr[u]){val[p]=0;while (p!=R){if (mp[p].count(u)){pq[p].push(make_pair(mp[p][u],u));mp[p].erase(u);}up(fa[p]);p=fa[p];}}else{val[p]=-oo;while (p!=R){up(fa[p]);p=fa[p];}}
}
int build(int l,int r)
{if (l==r) return tem[l];int mid=(l+r)/2,id=++n,x=build(l,mid),y=build(mid+1,r);clr[id]=1;if (l==mid) add(id,x,1);else add(id,x,0);if (mid+1==r) add(id,y,1);else add(id,y,0);return id;
}
void dfs4(int u,int fa)
{int tot=0,x,y,v;for (int i=0;i<t1[u].size();i++)if (t1[u][i]!=fa)tem[++tot]=t1[u][i];if (tot>2){int mid=(1+tot)/2;x=build(1,mid);y=build(mid+1,tot);add(u,x,0);if (tot==3) add(u,y,1);else add(u,y,0);}else for (int i=1;i<=tot;i++) add(u,tem[i],1);for (int i=0;i<t1[u].size();i++)if ((v=t1[u][i])!=fa)dfs4(v,u);
}
int main()
{//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);//printf("Elapsed time:%f secs.\n",(double)clock()/CLOCKS_PER_SEC);int u,v,x,q;char c;n=rd();for (int i=1;i<n;i++){u=rd();v=rd();t1[u].push_back(v);t1[v].push_back(u);}//printf("Elapsed time:%f secs.\n",(double)clock()/CLOCKS_PER_SEC);dfs4(1,-1);//printf("Elapsed time:%f secs.\n",(double)clock()/CLOCKS_PER_SEC);//for (int i=1;i<=n;i++) for (int j=fir[i];j;j=ne[j]) printf("(%d)%d->%d:%d\n",j/2,i,to[j],w[j]);clo=num;R=dfs1(1,n); //printf("Elapsed time:%f secs.\n",(double)clock()/CLOCKS_PER_SEC);q=rd();while (q--){c=rdc();if (c=='G') printf("%d\n",val[R]);else{u=rd();modi(u);}}//printf("Elapsed time:%f secs.\n",(double)clock()/CLOCKS_PER_SEC);
}