捉迷藏 Jiajia和Wind是一对恩爱的夫妻，并且他们有很多孩子。某天，Jiajia、Wind和孩子们决定在家里玩
捉迷藏游戏。他们的家很大且构造很奇特，由N个屋子和N-1条双向走廊组成，这N-1条走廊的分布使得任意两个屋
子都互相可达。游戏是这样进行的，孩子们负责躲藏，Jiajia负责找，而Wind负责操纵这N个屋子的灯。在起初的
时候，所有的灯都没有被打开。每一次，孩子们只会躲藏在没有开灯的房间中，但是为了增加刺激性，孩子们会要
求打开某个房间的电灯或者关闭某个房间的电灯。为了评估某一次游戏的复杂性，Jiajia希望知道可能的最远的两
个孩子的距离（即最远的两个关灯房间的距离）。 我们将以如下形式定义每一种操作： C(hange) i 改变第i个房
间的照明状态，若原来打开，则关闭；若原来关闭，则打开。 G(ame) 开始一次游戏，查询最远的两个关灯房间的
距离。

　　第一行包含一个整数N，表示房间的个数，房间将被编号为1,2,3…N的整数。接下来N-1行每行两个整数a, b，
表示房间a与房间b之间有一条走廊相连。接下来一行包含一个整数Q，表示操作次数。接着Q行，每行一个操作，如
上文所示。

　　对于每一个操作Game，输出一个非负整数到hide.out，表示最远的两个关灯房间的距离。若只有一个房间是关
着灯的，输出0；若所有房间的灯都开着，输出-1。

对于100%的数据， N ≤100000, M ≤500000。

  1 /*by SilverN*/  2 #include<algorithm>  3 #include<iostream>  4 #include<cstring>  5 #include<cstdio>  6 #include<cmath>  7 #include<vector>  8 #include<queue>  9 using namespace std; 10 const int mxn=100010; 11 int read(){ 12     int x=0,f=1;char ch=getchar(); 13     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 14     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 15     return x*f; 16 } 17 struct edge{int v,nxt;}e[mxn<<1]; 18 int hd[mxn],mct=0; 19 void add_edge(int u,int v){ 20     e[++mct].v=v;e[mct].nxt=hd[u];hd[u]=mct;return; 21 } 22 int n,m; 23 int light[mxn]; 24 struct Heap{ 25     priority_queue<int>hp,dl; 26     void push(int x){hp.push(x);} 27     void del(int x){dl.push(x);} 28     int size(){return hp.size()-dl.size();} 29     void pop(){ 30         while(!dl.empty() && dl.top()==hp.top()){dl.pop();hp.pop();} 31         hp.pop(); 32     } 33     int top(){ 34         while(!dl.empty() && dl.top()==hp.top()){dl.pop();hp.pop();} 35         return hp.top(); 36     } 37     int second(){ 38         int x=top();pop();    int y=top();push(x); 39         return y; 40     } 41 }s1[mxn],s2[mxn],s; 42 void insert(Heap &p){ 43     if(p.size()>=2){ 44         int tmp=p.top()+p.second(); 45         s.push(tmp); 46     } 47     return; 48 } 49 void Erase(Heap &p){ 50     if(p.size()>=2){ 51         int tmp=p.top()+p.second(); 52         s.del(tmp); 53     } 54     return; 55 } 56 int sz[mxn],mc[mxn],rt,smm; 57 bool vis[mxn]; 58 void DFS_sz(int u,int fa){ 59     sz[u]=1;mc[u]=0; 60     for(int i=hd[u];i;i=e[i].nxt){ 61         int v=e[i].v;if(vis[v] || v==fa)continue; 62         DFS_sz(v,u); 63         sz[u]+=sz[v]; 64         mc[u]=max(mc[u],sz[v]); 65     } 66     mc[u]=max(mc[u],smm-mc[u]); 67     if(mc[u]<mc[rt])rt=u; 68     return; 69 } 70 int f[mxn][20],dis[mxn][20]; 71 int dep[mxn]; 72 void getship(int u,int fa,int an,int d){ 73 //    printf("GS:u:%d fa:%d an:%d d:%d\n",u,fa,an,d); 74     for(int i=hd[u];i;i=e[i].nxt){ 75         int v=e[i].v;if(vis[v] || v==fa)continue; 76         f[v][++dep[v]]=an; 77         dis[v][dep[v]]=d; 78         getship(v,u,an,d+1); 79     } 80     return; 81 } 82 void solve(int x,int ff){ 83 //    printf("Rt:%d\n",x); 84     vis[x]=1; 85     getship(x,0,x,1); 86     for(int i=hd[x];i;i=e[i].nxt){ 87         if(vis[e[i].v])continue;int v=e[i].v; 88         rt=0;smm=sz[v]; 89         DFS_sz(v,0); 90         solve(rt,x); 91     } 92     return; 93 } 94 void update(int x,int mode){ 95 //    printf("update:%d  mode:%d\n",x,mode); 96     Erase(s2[x]); 97     if(!mode){s2[x].push(0);insert(s2[x]);} 98     else{s2[x].del(0);insert(s2[x]);} 99     for(int i=dep[x];i>1;i--){100 //        printf("anc%d : %d  dis:%d\n",i,f[x][i],dis[x][i]);101         if(!mode){//关灯 102             Erase(s2[f[x][i-1]]);103             104             if(s1[f[x][i]].size()) s2[f[x][i-1]].del(s1[f[x][i]].top());105             s1[f[x][i]].push(dis[x][i-1]);106             if(s1[f[x][i]].size()) s2[f[x][i-1]].push(s1[f[x][i]].top());107             108             insert(s2[f[x][i-1]]);109         }110         else{//开灯 111             Erase(s2[f[x][i-1]]);112             113             if(s1[f[x][i]].size()) s2[f[x][i-1]].del(s1[f[x][i]].top());114             s1[f[x][i]].del(dis[x][i-1]);115             if(s1[f[x][i]].size()) s2[f[x][i-1]].push(s1[f[x][i]].top());116             117             insert(s2[f[x][i-1]]);118         }119     }120     return;121 }122 int lcnt=0;123 int Que(){if(lcnt>1 && s.size())return s.top();else return lcnt-1;}124 int main(){125     int i,j,u,v;126     n=read();127     for(i=1;i<n;i++){128         u=read();v=read();129         add_edge(u,v);130         add_edge(v,u);131     }132     smm=n;133     mc[rt=0]=1e8;134     DFS_sz(1,0);135     solve(rt,0);136     lcnt=n;137     for(i=1;i<=n;i++)f[i][++dep[i]]=i;138     for(i=1;i<=n;i++)update(i,0);139     m=read();140     char op[5];141     while(m--){142         scanf("%s",op);143         if(op[0]==‘C‘){144             u=read();145             light[u]^=1;146             if(light[u])lcnt--;147             else lcnt++;148             update(u,light[u]);149         }150         else{151 //            printf("G!!\n");152             int ans=Que();153             printf("%d\n",ans);154         }155     }156     return 0;157 }