[ZJOI2007]Hide 捉迷藏

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。

题解：

第一次写动态点分。大概就是说，将每次求出来的重心建成一棵树，那么每修改一个点就要暴力的向上修改每一个重心的信息。（这里及以下的点都是指将重心建成一棵树之后的点）

我们不妨设关灯的点为黑点，开灯的点为白点。

这道题的正解是每个点维护两个个堆A，B如下：

　　A：记录点i及点i的子树中黑点到i的父节点的距离（大根堆）

　　B：记录点i的子节点的堆A的堆顶（大根堆）

　　C（答案堆）：记录所有点的堆B的最大值和次大值之和。

我们在建树的同时用数组记录一下一个节点的第1个父亲，第2个父亲......第x个父亲。

那么我们每修改一个点，就要将它和它的所有父亲修改（也就是从它到点分树根节点的那条链）。

答案就是C的堆顶。

那么对于这道题的空间复杂度，均摊下来是O(nlogn)的，所以不会炸

  1 //Never forget why you start
  2 #include<iostream>
  3 #include<cstdio>
  4 #include<cstdlib>
  5 #include<cstring>
  6 #include<cmath>
  7 #include<algorithm>
  8 #include<queue>
  9 #define inf (1e9)
 10 using namespace std;
 11 int n,m;
 12 struct node{
 13   int next,to;
 14 }edge[200005];
 15 struct Heap{
 16   priority_queue<int>a,b;
 17   void clean(){while(b.size()&&a.top()==b.top())a.pop(),b.pop();}
 18   void push(int x){a.push(x);}
 19   void erase(int x){b.push(x);}
 20   void pop(){clean();a.pop();}
 21   int top(){clean();if(a.size())return a.top();else return -inf;}
 22   int size(){return a.size()-b.size();}
 23   int s_top(){
 24     if(size()<2)return -inf;
 25     clean();
 26     int t=a.top(),ret;a.pop();
 27     clean();
 28     ret=a.top();a.push(t);
 29     return ret;
 30   }
 31 }A[100005],B[100005],C;
 32 int head[100005],size;
 33 void putin(int from,int to){
 34   size++;
 35   edge[size].next=head[from];
 36   edge[size].to=to;
 37   head[from]=size;
 38 }
 39 int root,tot,f[100005],cnt[100005],depth[100005],vis[100005],fa[100005][20],dis[100005][20];
 40 void getroot(int r,int fa){
 41   int i;
 42   cnt[r]=1;f[r]=0;
 43   for(i=head[r];i!=-1;i=edge[i].next){
 44     int y=edge[i].to;
 45     if(y!=fa&&!vis[y]){
 46       getroot(y,r);
 47       cnt[r]+=cnt[y];
 48       f[r]=max(f[r],cnt[y]);
 49     }
 50   }
 51   f[r]=max(f[r],tot-cnt[r]);
 52   if(f[root]>f[r])root=r;
 53 }
 54 void getship(int r,int tmp,int father,int dep){
 55   int i;
 56   for(i=head[r];i!=-1;i=edge[i].next){
 57     int y=edge[i].to;
 58     if(!vis[y]&&y!=father){
 59       fa[y][++depth[y]]=tmp;
 60       dis[y][depth[y]]=dep;
 61       getship(y,tmp,r,dep+1);
 62     }
 63   }
 64 }
 65 void buildtree(int r){
 66   int i;
 67   vis[r]=1;getship(r,r,0,1);int all=tot;
 68   for(i=head[r];i!=-1;i=edge[i].next){
 69     int y=edge[i].to;
 70     if(!vis[y]){
 71       if(cnt[y]>cnt[r])cnt[y]=all-cnt[r];tot=cnt[y];
 72       root=0;getroot(y,r);buildtree(root);
 73     }
 74   }
 75 }
 76 void turn_off(int r){//关掉一盏灯
 77   B[r].push(0);//这盏灯能作为路径的起点
 78   if(B[r].size()==2)C.push(B[r].top());//刚好等于2，说明正好有一条边
 79   for(int i=depth[r];i>1;i--){
 80     int t,pre;
 81     if(!A[fa[r][i]].size()){//如果A为空，那么加入的dis[r][i-1]一定是堆顶
 82       A[fa[r][i]].push(dis[r][i-1]);//更新A
 83       pre=B[fa[r][i-1]].top()+B[fa[r][i-1]].s_top();//记录当前B对C的贡献
 84       B[fa[r][i-1]].push(dis[r][i-1]);//更新B
 85       if(pre>0&&pre==B[fa[r][i-1]].top()+B[fa[r][i-1]].s_top())continue;//如果更新后的B对C的贡献不变，就continue
 86       if(pre>0&&pre!=B[fa[r][i-1]].top()+B[fa[r][i-1]].s_top())C.erase(pre),C.push(B[fa[r][i-1]].top()+B[fa[r][i-1]].s_top());
 87       //如果更新后的B对C的贡献改变，就更新C
 88       else if(B[fa[r][i-1]].top()+B[fa[r][i-1]].s_top()>0)C.push(B[fa[r][i-1]].top()+B[fa[r][i-1]].s_top());
 89       //如果B没有对C产生贡献，在加入了这个点之后有产生了贡献，就直接将贡献加进去
 90     }
 91     else{
 92       t=A[fa[r][i]].top();
 93       A[fa[r][i]].push(dis[r][i-1]);
 94       if(t<dis[r][i-1]){
 95     pre=B[fa[r][i-1]].top()+B[fa[r][i-1]].s_top();
 96     B[fa[r][i-1]].erase(t);B[fa[r][i-1]].push(dis[r][i-1]);
 97     if(pre>0&&pre!=B[fa[r][i-1]].top()+B[fa[r][i-1]].s_top())
 98       C.erase(pre),C.push(B[fa[r][i-1]].top()+B[fa[r][i-1]].s_top());
 99       }
100     }
101   }
102 }
103 void turn_on(int r){
104   B[r].erase(0);
105   if(B[r].size()==1)C.erase(B[r].top());
106   for(int i=depth[r];i>1;i--){
107     int t,pre;
108     A[fa[r][i]].erase(dis[r][i-1]);
109     if(A[fa[r][i]].top()<dis[r][i-1]){
110       pre=B[fa[r][i-1]].top()+B[fa[r][i-1]].s_top();
111       B[fa[r][i-1]].erase(dis[r][i-1]);
112       if(A[fa[r][i]].size())B[fa[r][i-1]].push(A[fa[r][i]].top());
113       if(pre>0&&pre!=B[fa[r][i-1]].top()+B[fa[r][i-1]].s_top()){
114     C.erase(pre);
115     if(B[fa[r][i-1]].size()>=2)
116       C.push(B[fa[r][i-1]].top()+B[fa[r][i-1]].s_top());
117       }
118     }
119   }
120 }
121 int now,on[100005];
122 void change(int x){
123   if(!on[x])turn_on(x);
124   else turn_off(x);
125   on[x]^=1;
126   if(on[x])now++;
127   else now--;
128 }
129 int main(){
130   int i,j;
131   scanf("%d",&n);
132   memset(head,-1,sizeof(head));
133   for(i=1;i<n;i++){
134     int from,to;
135     scanf("%d%d",&from,&to);
136     putin(from,to);
137     putin(to,from);
138   }
139   f[0]=inf;tot=n;getroot(1,0);buildtree(root);
140   for(i=1;i<=n;i++)fa[i][++depth[i]]=i,turn_off(i);
141   scanf("%d",&m);
142   char s[5];
143   while(m--){
144     scanf("%s",s);
145     if(s[0]=='G'){
146       if(now==n)printf("-1
");
147       else printf("%d
",max(C.top(),0));
148     }
149     else{
150       scanf("%d",&j);
151       change(j);
152     }
153   }
154   return 0;
155 }