题解 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大神博客里写的这个技巧）

于是我们就用常数更小的堆代替了线段树和平衡树，而且维护起来也更方便了，代码瞬间短了许多。

上代码~

#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);
}