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

8

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

4

3

3

4

HINT

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

Solution

维护三个堆。

$h1[x]$存当前重心$x$管辖的范围内的点到$x$在点分树上的父亲的所有距离。

$h2[x]$存$x$在点分树上所有儿子的$h1$堆的堆顶。

$h3$存每个点的答案。

关灯的点$h2$自带一个$0$方便处理单链……

反正快退役了也不想写太多了……还有问题看代码吧……

Code

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #define N (100009)  6 using namespace std;  7   8 struct Heap  9 { 10     priority_queue
         
          q,del; 11     void push(int x) {q.push(x);} 12     void erase(int x) {del.push(x);} 13     bool empty() {
   return q.size()-del.size()==0;} 14     int size() {
   return q.size()-del.size();} 15     int top() 16     { 17         while (!del.empty() && q.top()==del.top()) q.pop(), del.pop(); 18         return q.top(); 19     } 20     void pop() 21     { 22         while (!del.empty() && q.top()==del.top()) q.pop(), del.pop(); 23         return q.pop(); 24     } 25     int sec() 26     { 27         if (size()<2) return -1; 28         int tmp1=top(); pop(); 29         int tmp2=top(); push(tmp1); 30         return tmp2; 31     } 32 }h1[N],h2[N],h3; 33  34 struct Edge{
   int to,next;}edge[N<<1]; 35 int n,m,root,sum,light_num; 36 int s[N],f[N][17],fa[N],dep[N],maxsize[N],size[N],vis[N]; 37 int head[N],num_edge; 38  39 inline int read() 40 { 41     int x=0,w=1; char c=getchar(); 42     while (c<'0' || c>'9') {
   if (c=='-') w=-1; c=getchar();} 43     while (c>='0' && c<='9') x=x*10+c-'0', c=getchar(); 44     return x*w; 45 } 46  47 void add(int u,int v) 48 { 49     edge[++num_edge].to=v; 50     edge[num_edge].next=head[u]; 51     head[u]=num_edge; 52 } 53  54 void DFS(int x,int fa) 55 { 56     dep[x]=dep[fa]+1; f[x][0]=fa; 57     for (int i=1; i<=16; ++i) f[x][i]=f[f[x][i-1]][i-1]; 58     for (int i=head[x]; i; i=edge[i].next) 59         if (edge[i].to!=fa) DFS(edge[i].to,x); 60 } 61  62 void Get_Root(int x,int fa) 63 { 64     size[x]=1; maxsize[x]=0; 65     for (int i=head[x]; i; i=edge[i].next) 66         if (!vis[edge[i].to] && edge[i].to!=fa) 67         { 68             Get_Root(edge[i].to,x); 69             size[x]+=size[edge[i].to]; 70             maxsize[x]=max(maxsize[x], size[edge[i].to]); 71         } 72     maxsize[x]=max(maxsize[x],sum-size[x]); 73     if (maxsize[x]
          
           =0; --i) 92 if (dep[f[x][i]]>=dep[y]) x=f[x][i]; 93 if (x==y) return x; 94 for (int i=16; i>=0; --i) 95 if (f[x][i]!=f[y][i]) x=f[x][i], y=f[y][i]; 96 return f[x][0]; 97 } 98 99 void Insert(int x)100 {101 if (h2[x].size()>=2)102 h3.push(h2[x].top()+h2[x].sec());103 }104 105 106 void Delete(int x)107 {108 if (h2[x].size()>=2)109 h3.erase(h2[x].top()+h2[x].sec());110 }111 112 void Turn_off(int x)113 {114 Delete(x); h2[x].push(0); Insert(x);115 light_num--;116 for (int t=x,ft=fa[t]; ft; t=fa[t],ft=fa[t])117 {118 Delete(ft);119 if (!h1[t].empty()) h2[ft].erase(h1[t].top());120 h1[t].push(dep[x]+dep[ft]-2*dep[LCA(x,ft)]);121 h2[ft].push(h1[t].top());122 Insert(ft);123 }124 }125 126 void Turn_on(int x)127 {128 Delete(x); h2[x].erase(0); Insert(x);129 light_num++;130 for (int t=x,ft=fa[t]; ft; t=fa[t],ft=fa[t])131 {132 Delete(ft);133 if (!h1[t].empty()) h2[ft].erase(h1[t].top());134 h1[t].erase(dep[x]+dep[ft]-2*dep[LCA(x,ft)]);135 if (!h1[t].empty()) h2[ft].push(h1[t].top());136 Insert(ft);137 }138 }139 140 int main()141 {142 n=read(); sum=maxsize[0]=n;143 for (int i=1; i<=n-1; ++i)144 {145 int u=read(),v=read();146 add(u,v); add(v,u);147 }148 DFS(1,0);149 Get_Root(1,0);150 Solve(root);151 for (int i=1; i<=n; ++i) Turn_off(i);152 light_num=0;153 m=read();154 while (m--)155 {156 char opt=getchar();157 while (opt!='C' && opt!='G') opt=getchar();158 if (opt=='C')159 {160 int x=read();161 if (!s[x]) Turn_on(x);162 else Turn_off(x);163 s[x]^=1;164 }165 else166 {167 if (light_num>=n-1) puts(light_num==n?"-1":"0");168 else printf("%d\n",h3.top());169 }170 }171 }