题解 P2056 【[ZJOI2007]捉迷藏 】

作为一道动态点分治板子题，这题题解里没动态点分治解法真是不科学。~~虽然这东西多带一个log……~~ 大致的思路就是我们在静态的点分治的基础上维护一个高度为$O(logn)$的树形结构，这棵树上的点为当前做点分治时这个连通块的重心，应该是很好想的毕竟分治本身就是个树形结构，我们把这个树形结构具体实现出来了而已。我们把这个树形结构称作点分树。 然后我们在点分树上维护一些奇奇怪怪的信息，就能够支持带动态修改的和普通点分治一样的路径信息统计了。因为修改的时候只需要考虑这个点在点分树上到根的路径上的点，而树高是$O(logn)$的就暴力跳就行了。 关于如何在点分树上维护这里写两种方法： **方法1.**（~~这其实是我自己YY出来的……~~）普通点分治是以当前连通块的重心为根，然后逐个扫一遍他的儿子做类似于dp一样的东西，这其中的关键就是 **以重心为根合并他的两个儿子的子树** ，显然，我们需要在当前连通块的重心处用个支持删除的logn数据结构维护他所有儿子（这里说的都是原来树上的儿子，别和点分树上的儿子搞混了）子树内的关灯点到重心的距离的最大值和次大值，显然这两个加起来就是过这个点所有合法路径的最大值。而他的儿子的子树如何分开维护呢？我们可以用$dfs$序把儿子的子树当成一个区间，然后在这个重心上用动态开点线段树维护（显然这样做空间复杂度是$O(nlogn)$的）$dfs$序区间内的最大值，然后再在重心上开一棵平衡树维护这些区间的最大值。那么他点分树上的子树的答案呢？我们再开一棵平衡树维护点分树上子树的答案最大值，再用这棵平衡树的最大值更新点分树上父亲的答案。然后就可以在修改的时候维护这3棵树了，时间复杂度$O(nlog^2n)$，空间复杂度$O(nlogn)$。 然后这个方法代码极长（我目前写过的最长代码……），过于毒瘤，这还不算——它常数太大了，毕竟我们要同时在一条到根的链上维护3个数据结构，这其中还有个常数大的吓人的动态开点线段树……实测最后一个点过不去…… ~~代码过于毒瘤就不放了……~~ **方法2.** 我们其实可以换一种思路统计答案，方法1说了我们得在重心处合并两个子树的答案，而子树我们还得在这一层想办法维护。但是我们发现**每个子树可是要在分治的下一层作为一个整体的连通块的**，那么我们可以在点分治的时候考虑他在点分树上的父亲$fa$，我们维护当前连通块内所有关灯点到$fa$距离的最大值，记为$mxdis_i$，然后我们在$fa$处维护他点分树的儿子的$mxdis_i$的最大值和次大值，就是这个点的答案了。至于维护总体的答案其实也不用在树上每个点都维护一遍，在全局用个数据结构维护就行了。注意维护点分树儿子最大的$mxdis_i$的时候，如果自己是关着灯的就得再额外插入一个0，因为自己也可以是端点。 另外这个数据结构需要支持查最大值、次大值和删除，其实可以不用平衡树，我们用一个两个大根堆$A$和$B$构成的玩意就可以维护。删除的时候并不考虑$A$的删除，而是把这个数插到$B$内，查最大值的时候如果发现$A$的堆顶和$B$的堆顶一样就说明这个数被删除过了，就同时弹掉。（感谢$PoPoQQQ$大神博客里写的这个技巧） 于是我们就用常数更小的堆代替了线段树和平衡树，而且维护起来也更方便了，代码瞬间短了许多。 上代码~ ```cpp #include<iostream> #include<cstdio> #include<cstring> #include<queue> #define inf 123456789 using namespace std; namespace ywy{ inline int get(){//我的垃圾快读 int n=0;char c;while((c=getchar())||23333){ if(c>='0'&&c<='9')break;if(c=='-')goto s; }n=c-'0';while((c=getchar())||23333){ if(c>='0'&&c<='9')n=n*10+c-'0';else return(n); }s:while((c=getchar())||23333){ if(c>='0'&&c<='9')n=n*10-c+'0';else return(n); } } void print(int num){ if(num>=10)print(num/10);putchar(num%10+'0'); } inline char cget(){ char c;while((c=getchar())||23333)if(c>='A'&&c<='Z')return(c); } int heads[100001]； int fa[100001];//点分树上的父亲 int size[100001];//当前的子树大小，找重心用的 int que[100001]; unsigned char bv[100001];//点分治的时候这个点是否被solve了 typedef struct _dui{//把这两个大根堆构成的玩意封装起来 priority_queue<int> me,del;//del存删除的信息 inline int getmax(){ while(!me.empty()&&(!del.empty()&&me.top()==del.top()))me.pop(),del.pop();//弹出已经删除的堆顶 if(me.empty())return(-inf);return(me.top()); } inline void remove(int num){ if(me.top()==num)me.pop();else del.push(num); } inline void insert(int num){ me.push(num); } inline int getsecond(){ int cjr=getmax();if(cjr==-inf)return(-inf);me.pop();int ywy=getmax();me.push(cjr);return(ywy); } }dui; dui globe；//维护全局的答案 dui fuqin[100001];//维护当前连通块关灯的点到点分树父亲的最大距离 dui chs[100001];//维护儿子（当然也包括自己）最大的maxdis typedef struct _b{ int dest;int nxt; }bian; bian memchi[200001]; int gn=1; inline void add(int s,int t){ memchi[gn].dest=t;memchi[gn].nxt=heads[s];heads[s]=gn;gn++; } int dis[100001][18];//当前分治到这个深度时，到点分树父亲的距离 int rdeep[100001];//作为重心时的分治深度 unsigned char zt[100001];//是否关灯 int gdeep,tot,zx; inline void bfs(int pt){//bfs求出距离 tot=0; register int head=0,tail=1; que[0]=pt; dis[pt][gdeep]=1; do{ int me=que[head];head++;tot++; for(register int i=heads[me];i;i=memchi[i].nxt){ if(bv[memchi[i].dest])continue; if(dis[me][gdeep]+1<dis[memchi[i].dest][gdeep]){ dis[memchi[i].dest][gdeep]=dis[me][gdeep]+1; que[tail]=memchi[i].dest;tail++; } } }while(head<tail); } void afs(int pt,int baba){//找重心 size[pt]=1; int mx=0; for(register int i=heads[pt];i;i=memchi[i].nxt){ if(bv[memchi[i].dest]||memchi[i].dest==baba)continue; afs(memchi[i].dest,pt); size[pt]+=size[memchi[i].dest]; mx=max(mx,size[memchi[i].dest]); } if(max(mx,tot-size[pt])<=tot/2)zx=pt; } int lstans[100001];//存放这个点的答案，方便维护全局的堆 int hexin; void digui(int pt,int baba,int dp){//点分治 gdeep=dp; bfs(pt); afs(pt,0); if(!baba)hexin=zx; rdeep[zx]=dp; if(baba){ for(register int i=0;i<tot;i++)fuqin[zx].insert(dis[que[i]][dp]);//维护maxdis } fa[zx]=baba; int me=zx;bv[zx]=1; for(register int i=heads[zx];i;i=memchi[i].nxt){ if(bv[memchi[i].dest])continue; digui(memchi[i].dest,me,dp+1); } if(baba)chs[baba].insert(fuqin[me].getmax());//把maxdis插入父亲 chs[me].insert(0);//别忘了维护自己 globe.insert(lstans[me]=chs[me].getmax()+chs[me].getsecond());//当前点的答案 } void ywymain(){ memset(dis,0x7f,sizeof(dis)); int n=get(); for(register int i=1;i<n;i++){ int s=get(),t=get();add(s,t);add(t,s); } digui(1,0,0); int q=get(); int guan=n;//有多少灯关着 while(q){ q--; char cmd=cget(); if(cmd=='G'){ if(guan==1)printf("0\n");else{ if(guan==0)printf("-1\n"); else print(globe.getmax()),putchar('\n'); } }else{ int x=get(); if(zt[x])chs[x].insert(0),guan++;//这个灯关了就要额外插入0 else chs[x].remove(0),guan--; int cur=x; while(cur){ int cjr=chs[cur].getmax()+chs[cur].getsecond(); if(cjr!=lstans[cur]){ globe.remove(lstans[cur]); globe.insert(lstans[cur]=cjr);//更新全局答案 }if(!fa[cur])break; int dp=rdeep[cur]; cjr=fuqin[cur].getmax(); if(zt[x])fuqin[cur].insert(dis[x][dp]); else fuqin[cur].remove(dis[x][dp]);//维护到点分树父亲的距离 int ywy=fuqin[cur].getmax(); if(ywy!=cjr){ chs[fa[cur]].remove(cjr); chs[fa[cur]].insert(ywy); } cur=fa[cur]; } zt[x]^=1; } } } } int main(){ ywy::ywymain();return(0); } ```