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。
Sample Input
1 2
2 3
3 4
3 5
3 6
6 7
6 8
7
G
C 1
G
C 2
G
C 1
G
Sample Output
3
3
4
HINT
对于100%的数据， N ≤100000, M ≤500000。
动态点分治
它的主要思想就是通过将的重心相连来维护一棵“点分树”，通过“点分树”中各个节点与其儿子间的联系来实现在线修改和查询的目的。
这样修改一个点只要顺着父亲跳并更新，显然点分树深度不超过logn
经过一个点的答案显然是一个子树最远的黑点+另一个子树最远的黑点
可以令q1[x]堆表示点到x的上一个根的距离
这样q2[pa]堆维护pa的子树中的最大距离，q2[pa].push(q1[x].top())
q3堆表示答案，用q2[x]中的最大值和次大值和插入
不过q2[x]要插入0，以免出现路径没有超过x的情况没有统计
修改的话：开灯操作就是把q2[x]堆中的0删掉，因为路径不能在x停下
然后从下往上更新，把q1[i]堆中与x到fa[i]的距离删掉
每一步都要重新计算q2，q3
关灯同理，加入0，把距离加入
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
const int N=;
struct Node
{
int next,to;
}edge[*N+];
int head[N+],num,fa[N+][],dep[N+],size[N+],maxsize[N+],minsize,root,FA[N+],n,m,cnt;
int light[N+];
char ch[];
bool vis[N+];
struct Heap
{
priority_queue<int>q,p;
void push(int x)
{q.push(x);}
void erase(int x)
{p.push(x);}
int top()
{
while (!q.empty()&&!p.empty()&&q.top()==p.top()) q.pop(),p.pop();
return q.top();
}
int sec()
{
while (!q.empty()&&!p.empty()&&q.top()==p.top()) q.pop(),p.pop();
int tmp=q.top();q.pop();
while (!q.empty()&&!p.empty()&&q.top()==p.top()) q.pop(),p.pop();
int val=q.top();
q.push(tmp);
return val;
}
int size()
{
return q.size()-p.size();
}
}q1[],q2[],q3;
void add(int u,int v)
{
num++;
edge[num].next=head[u];
head[u]=num;
edge[num].to=v;
}
void dfs(int x,int pa)
{int i;
fa[x][]=pa;
dep[x]=dep[pa]+;
for (i=head[x];i;i=edge[i].next)
{
int v=edge[i].to;
if (v==pa) continue;
dfs(v,x);
}
}
int lca(int x,int y)
{int i;
if (dep[x]<dep[y]) swap(x,y);
for (i=;i>=;i--)
if (dep[x]-(<<i)>=dep[y]) x=fa[x][i];
if (x==y) return x;
for (i=;i>=;i--)
if (fa[x][i]!=fa[y][i])
{
x=fa[x][i];
y=fa[y][i];
}
return fa[x][];
}
void get_size(int x,int pa)
{int i;
size[x]=;
maxsize[x]=;
for (i=head[x];i;i=edge[i].next)
{
int v=edge[i].to;
if (vis[v]||v==pa) continue;
get_size(v,x);
size[x]+=size[v];
if (maxsize[x]<size[v]) maxsize[x]=size[v];
}
}
void get_root(int x,int r,int pa)
{int i;
maxsize[x]=max(maxsize[x],size[r]-size[x]);
if (minsize>maxsize[x])
{
minsize=maxsize[x];
root=x;
}
for (i=head[x];i;i=edge[i].next)
{
int v=edge[i].to;
if (v==pa||vis[v]) continue;
get_root(v,r,x);
}
}
int dist(int x,int y)
{
int z=lca(x,y);
return dep[x]+dep[y]-*dep[z];
}
void get_dist(int x,int pa,int fa)
{int i;
q1[root].push(dist(pa,x));
for (i=head[x];i;i=edge[i].next)
{
int v=edge[i].to;
if (v==fa||vis[v]) continue;
get_dist(v,pa,x);
}
}
void work(int x,int pa)
{int i;
minsize=2e9;
get_size(x,);get_root(x,x,);
FA[root]=pa;vis[root]=;
q2[root].push();q1[root].push(dist(root,pa));
for (i=head[root];i;i=edge[i].next)
{
int v=edge[i].to;
if (vis[v]) continue;
get_dist(v,pa,root);
}
q2[pa].push(q1[root].top());
int rt=root;
for (i=head[root];i;i=edge[i].next)
{
int v=edge[i].to;
if (vis[v]) continue;
work(v,rt);
}
if (q2[rt].size()>=)
q3.push(q2[rt].top()+q2[rt].sec());
}
void trunon(int x)
{int i;
if (q2[x].size()>=)
q3.erase(q2[x].top()+q2[x].sec());
q2[x].erase();
if (q2[x].size()>=)
q3.push(q2[x].top()+q2[x].sec());
for (i=x;FA[i];i=FA[i])
{
if (q2[FA[i]].size()>=) q3.erase(q2[FA[i]].top()+q2[FA[i]].sec());
if (q1[i].size()) q2[FA[i]].erase(q1[i].top());
q1[i].erase(dist(x,FA[i]));
if (q1[i].size()) q2[FA[i]].push(q1[i].top());
if (q2[FA[i]].size()>=) q3.push(q2[FA[i]].top()+q2[FA[i]].sec());
}
}
void trunoff(int x)
{int i;
if (q2[x].size()>=)
q3.erase(q2[x].top()+q2[x].sec());
q2[x].push();
if (q2[x].size()>=)
q3.push(q2[x].top()+q2[x].sec());
for (i=x;FA[i];i=FA[i])
{
if (q2[FA[i]].size()>=) q3.erase(q2[FA[i]].top()+q2[FA[i]].sec());
if (q1[i].size()) q2[FA[i]].erase(q1[i].top());
q1[i].push(dist(x,FA[i]));
if (q1[i].size()) q2[FA[i]].push(q1[i].top());
if (q2[FA[i]].size()>=) q3.push(q2[FA[i]].top()+q2[FA[i]].sec());
}
}
int main()
{int i,u,v,j,x;
cin>>n;
for (i=;i<=n-;i++)
{
scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
cin>>m;
dfs(,);
for (i=;i<=;i++)
{
for (j=;j<=n;j++)
fa[j][i]=fa[fa[j][i-]][i-];
}
work(,);
cnt=n;
for (i=;i<=m;i++)
{
scanf("%s",ch);
if (ch[]=='G')
{
if (cnt<=) printf("%d\n",cnt-);
else printf("%d\n",q3.top());
}
else
{
scanf("%d",&x);
if (light[x]==) trunon(x),cnt--;
else trunoff(x),cnt++;
light[x]^=;
}
}
}