首页 > 代码库 > 【BZOJ1095】【ZJOI2007】捉迷藏 [动态点分治]
【BZOJ1095】【ZJOI2007】捉迷藏 [动态点分治]
捉迷藏
Time Limit: 40 Sec Memory Limit: 256 MB[Submit][Status][Discuss]
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，输出一个非负整数，表示最远的两个关灯房间的距离。若只有一个房间是关着灯的，输出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。
Main idea
给定一棵树，有0点或者1点，每次查询最远的两个1点之间的距离，需要支持修改0和1。
Source
我们先观察一下数据，由于n<=10^5，所以O(n^2)的做法不可行。我们先考虑如何静态查询，首先我们第一反应想到了树形DP，然后发现这种方法无法优化。考虑一下有什么方法是log级别的呢？我们想到了点分，静态点分的做法就是每次取出重心，然后查询最深的1点的深度即可，要如何优化呢？发现如果点分可以动态实现的话就可以AC了。那么现在确定了算法：动态点分治。
我们先从点分的角度来剖析一下，点分其实就相当于每次找到重心，处理和重心有关的路径，然后把重心割掉，将树分为多个小块，这样将所有路径上的信息存到了重心上，降低规模处理问题，有效降低复杂度。那么动态点分治就相当于用线段树处理序列问题一样，在分治的框架上加上了对于每个点的信息维护，对于每个点用堆来维护信息，这样来实现信息的维护与查询。
我们分几步来实现：
1. 建立“重心树”：我们发现我们在点分中重心存着路径的信息，所以我们只要维护跟重心有关的信息就可以了，考虑到分治过程的性质，所以修改了一个点，只会影响到这个点作为一个重心时以上的重心（以下称为“父重心”），所以我们先根据找重心的过程建立一棵“重心树”，一个点（作为重心时）隔开后得到的若干棵子树中的每一个重心的父重心就是这个点（这个点称为“子重心”），所以可以证明这棵树的深度是log级别的。每次只需要修改这个点在重心树中到根的路径上的点。
2. 构建可删堆：由于我们要维护的是最长链，思考静态的时候要维护的就是最大值，那么动态时我们就需要一个数据结构来维护这些最大值，支持更改与删除等操作，我们想到了“堆”，由于这个堆是需要支持删除操作的，这里讨论一下怎么删除：对于每个heap堆再开一个del堆，删除一个点的时候将要删除的值加入到del堆里面，然后调取top的时候如果heap堆和del堆的堆顶是一样的同时pop掉，直到不一样的时候的top就是真正的top了，其余操作类似。
3. 维护信息：对于每个点开两个堆维护信息，第一个c堆维护“这个重心的子树（包括这个重心）到父重心的距离”（求距离用LCA即可），第二个b堆维护“这个重心隔开后的几个子树中的最大深度（也就是子重心c堆的堆顶）”，然后全局开一个A堆维护“每一个b堆的最大值和次大值”，那么显然答案就是堆A的top。
4. 修改操作：这里讨论一下将1点变为0点的操作（0变为1类似），每次修改一个点显然需要直接影响到c堆，将在重心树中到根位置的中的点的c堆中删除掉这个点的值，就会影响到b堆，然后最终影响到A堆。每次修改先删除掉堆A的top，然后在父重心的b堆中删除掉这个点的c堆的top，删除掉这个c堆的top，然后再在父重心的b堆中加入这个点的c堆的top即可，修改的时候再维护一下A堆即可，处理一下细节。
Code
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cstring> 5 #include<cstdlib> 6 #include<cmath> 7 #include<queue> 8 using namespace std; 9 10 const int ONE=100005; 11 12 int n,T; 13 int x,y; 14 int next[ONE*2],first[ONE*2],go[ONE*2],tot; 15 int Dep[ONE],Turnoff[ONE],Light; 16 int fat[ONE]; 17 int f[ONE][21]; 18 char ch[10]; 19 20 int get() 21 { 22 int res,Q=1; char c; 23 while( (c=getchar())<48 || c>57) 24 if(c==‘-‘)Q=-1; 25 if(Q) res=c-48; 26 while((c=getchar())>=48 && c<=57) 27 res=res*10+c-48; 28 return res*Q; 29 } 30 31 int Add(int u,int v) 32 { 33 next[++tot]=first[u]; first[u]=tot; go[tot]=v; 34 next[++tot]=first[v]; first[v]=tot; go[tot]=u; 35 } 36 37 38 struct Heap_deal 39 { 40 priority_queue <int> heap,delet; 41 42 void add(int x) {heap.push(x);} 43 void del(int x) {delet.push(x);} 44 void Pop() 45 { 46 while(!delet.empty() && heap.top()==delet.top()) 47 { 48 heap.pop(); 49 delet.pop(); 50 } 51 heap.pop(); 52 } 53 54 int Top() 55 { 56 while(!delet.empty() && heap.top()==delet.top()) 57 { 58 heap.pop(); 59 delet.pop(); 60 } 61 return heap.top(); 62 } 63 64 int SecondTop() 65 { 66 int jilu1=Top(); Pop(); 67 int jilu2=Top(); add(jilu1); 68 return jilu2; 69 } 70 71 int Size() 72 { 73 return heap.size()-delet.size(); 74 } 75 }A,b[ONE],c[ONE]; 76 77 void ADD(Heap_deal &a) 78 { 79 if(a.Size()>=2) 80 { 81 int r1=a.Top(); 82 int r2=a.SecondTop(); 83 A.add( r1+r2 ); 84 } 85 } 86 87 void DEL(Heap_deal &a) 88 { 89 if(a.Size()>=2) 90 { 91 int r1=a.Top(); 92 int r2=a.SecondTop(); 93 A.del( r1+r2 ); 94 } 95 } 96 97 namespace PartLCA 98 { 99 void Deal_first(int u,int father)100 {101 Dep[u]=Dep[father]+1;102 for(int i=0;i<=19;i++)103 {104 f[u][i+1]=f[f[u][i]][i];105 }106 107 for(int e=first[u];e;e=next[e])108 {109 int v=go[e];110 if(v==father) continue;111 f[v][0]=u;112 Deal_first(v,u);113 }114 }115 116 int LCA(int x,int y)117 {118 if(Dep[x]<Dep[y]) swap(x,y);119 for(int i=20;i>=0;i--)120 {121 if(Dep[f[x][i]]>=Dep[y]) x=f[x][i];122 if(x==y) return x;123 }124 125 for(int i=20;i>=0;i--)126 {127 if(f[x][i]!=f[y][i])128 {129 x=f[x][i];130 y=f[y][i];131 }132 }133 return f[x][0];134 }135 136 int dist(int x,int y)137 {138 return Dep[x]+Dep[y]-2*Dep[LCA(x,y)];139 }140 }141 142 143 namespace PointF144 {145 int Min,center,vis_center[ONE];146 147 struct power148 {149 int size,maxx;150 }S[ONE];151 152 153 void Getsize(int u,int father)154 {155 S[u].size=1;156 S[u].maxx=0;157 for(int e=first[u];e;e=next[e])158 {159 int v=go[e];160 if(v==father || vis_center[v]) continue;161 Getsize(v,u);162 S[u].size+=S[v].size;163 S[u].maxx=max(S[u].maxx,S[v].size);164 }165 }166 167 void Getcenter(int u,int father,int total)168 {169 S[u].maxx=max(S[u].maxx,total-S[u].size);170 if(S[u].maxx<Min)171 {172 Min=S[u].maxx;173 center=u;174 }175 176 for(int e=first[u];e;e=next[e])177 {178 int v=go[e];179 if(v==father || vis_center[v]) continue;180 Getcenter(v,u,total);181 }182 }183 184 void Add_c(int u,int father,int center)185 {186 c[center].add(PartLCA::dist(u,fat[center]));187 for(int e=first[u];e;e=next[e])188 {189 int v=go[e];190 if(v==father || vis_center[v]) continue;191 Add_c(v,u,center);192 }193 }194 195 196 void New_tree(int u,int Last)197 {198 Min=n;199 Getsize(u,0);200 Getcenter(u,0,S[u].size);201 vis_center[center]=1;202 203 fat[center]=Last;204 if(Last!=0) Add_c(center,0,center);205 if(c[center].Size()) b[Last].add(c[center].Top());206 207 int root=center;208 for(int e=first[center];e;e=next[e])209 {210 int v=go[e];211 if(vis_center[v]) continue;212 New_tree(v,root);213 }214 }215 }216 217 namespace Control218 {219 void Turn_off(int x)220 {221 for(int i=x;fat[i];i=fat[i])222 {223 DEL(b[fat[i]]);224 if(c[i].Size()) b[fat[i]].del(c[i].Top());225 226 c[i].del(PartLCA::dist(fat[i],x));227 228 if(c[i].Size()) b[fat[i]].add(c[i].Top());229 ADD(b[fat[i]]);230 }231 }232 233 void Turn_on(int x)234 {235 for(int i=x;fat[i];i=fat[i])236 {237 DEL(b[fat[i]]);238 if(c[i].Size()) b[fat[i]].del(c[i].Top());239 240 c[i].add(PartLCA::dist(fat[i],x));241 242 if(c[i].Size()) b[fat[i]].add(c[i].Top());243 ADD(b[fat[i]]);244 }245 }246 }247 248 249 int main()250 {251 n=get();252 Light=n;253 for(int i=1;i<=n;i++) Turnoff[i]=1;254 for(int i=1;i<n;i++)255 {256 x=get(); y=get();257 Add(x,y);258 }259 260 PartLCA::Deal_first(1,0);261 PointF::New_tree(1,0);262 263 for(int i=1;i<=n;i++) ADD(b[i]);264 265 T=get();266 while(T--)267 {268 scanf("%s",ch);269 if(ch[0]==‘G‘)270 {271 if(Light==0) printf("-1");272 else if(Light==1) printf("0");273 else printf("%d",A.Top());274 printf("\n");275 }276 277 if(ch[0]==‘C‘)278 {279 x=get();280 if(Turnoff[x])281 {282 Turnoff[x]=0;283 Light--;284 Control::Turn_off(x);285 }286 else287 {288 Turnoff[x]=1;289 Light++;290 Control::Turn_on(x);291 }292 }293 }294 }
【BZOJ1095】【ZJOI2007】捉迷藏 [动态点分治]