BZOJ1095:[ZJOI2007]Hide 捉迷藏(动态点分治)-布布扣-bubuko.com

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

HINT

Solution

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

Code

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 #include<queue>
  5 #define N (100009)
  6 using namespace std;
  7 
  8 struct Heap
  9 {
 10     priority_queue<int>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]<maxsize[root]) root=x;
 74 }
 75 
 76 void Solve(int x)
 77 {
 78     vis[x]=1;
 79     for (int i=head[x]; i; i=edge[i].next)
 80         if (!vis[edge[i].to])
 81         {
 82             sum=size[edge[i].to]; root=0;
 83             Get_Root(edge[i].to,x);
 84             fa[root]=x; Solve(root);
 85         }
 86 }
 87 
 88 int LCA(int x,int y)
 89 {
 90     if (dep[x]<dep[y]) swap(x,y);
 91     for (int i=16; i>=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         else
166         {
167             if (light_num>=n-1) puts(light_num==n?"-1":"0");
168             else printf("%d\n",h3.top());
169         }
170     }
171 }

原文：https://www.cnblogs.com/refun/p/10644850.html