[BZOJ 1095][ZJOI2007]Hide 捉迷藏

题意

给定一棵 \(n\) 个点的树以及 \(q\) 次操作. 操作有两种, 一种是求有效点之间的最大距离, 另一种是将一个点的有效状态反转.

\(n\le 1\times 10^5,q\le 5\times 10^5\).

题解

好像老老实实写动态点分的在榜上都垫底了qaq

我们可以发现这个求两点之间最大距离非常的点分治, 为了处理修改有效点的问题, 我们需要动态点分治.

首先我们把点分树建出来, 接下来的操作对点分树进行(距离按原树算).

然后对于每个点, 我们记录两个平衡树/堆, 一个 \(len\) 表示这个子树中的所有点到根的父亲的距离, 一个 \(maxd\) 表示各个子结点的 \(len\) 中的最大值. 全局再维护一个 \(all\) 存储每个点的 \(maxd\) 中的最大值与次大值之和.

不难发现每次查询的时候取 \(all\) 中的最大值即是答案.

修改的时候距离用LCA计算, 每次先把当前点可能产生的贡献删除, 修改后再插回去.

初始化的时候有个技巧, DFS当前分治子树的时候 \(dis[root]\) 保存的是父分治子树的根到当前点的距离. 发现这刚好就是我们要算的东西, 直接insert进set就好了.

复杂度 \(O((n+q)\log^2 n)\).

参考代码

#include <bits/stdc++.h>

const int MAXV=1e5+10;
const int MAXE=2e5+10;
typedef std::multiset<int,std::greater<int>> multiset;

struct Edge{
    int from;
    int to;
    Edge* next;
};
Edge E[MAXE];
Edge* head[MAXV];
Edge* topE=E;

int n;
int q;
int root;
int cursize;
int prt[MAXV];
int dis[MAXV];
int top[MAXV];
int son[MAXV];
int size[MAXV];
int pprt[MAXV];
int deep[MAXV];
bool off[MAXV];
bool vis[MAXV];
int msize[MAXV];

multiset all;
multiset len[MAXV];
multiset maxd[MAXV];

char GetCmd();
int ReadInt();
void Solve(int);
int Dis(int,int);
int LCA(int,int);
void DFS(int,int);
void Insert(int,int);
void Modify(int,bool);
void DFS(int,int,int);
void GetRoot(int,int);
int Export(const multiset&);

int main(){
    n=ReadInt();
    for(int i=1;i<n;i++){
        int a=ReadInt(),b=ReadInt();
        Insert(a,b);
        Insert(b,a);
    }
    DFS(1,0,0);
    DFS(1,1);
    cursize=n;
    msize[0]=n;
    GetRoot(1,0);
    Solve(root);
    q=ReadInt();
    while(q--){
        if(GetCmd()=='C'){
            int x=ReadInt();
            Modify(x,off[x]^=1);
        }
        else
            printf("%d\n",*all.begin());
    }
    return 0;
}

void Modify(int x,bool opt){
    if(maxd[x].size()>1)
        all.erase(all.find(Export(maxd[x])));
    if(opt)
        maxd[x].erase(maxd[x].find(0));
    else
        maxd[x].insert(0);
    if(maxd[x].size()>1)
        all.insert(Export(maxd[x]));
    for(int p=x;prt[p]!=0;p=prt[p]){
        if(maxd[prt[p]].size()>1)
            all.erase(all.find(Export(maxd[prt[p]])));
        if(!len[p].empty())
            maxd[prt[p]].erase(maxd[prt[p]].find(*len[p].begin()));
        if(opt)
            len[p].erase(len[p].find(Dis(prt[p],x)));
        else
            len[p].insert(Dis(prt[p],x));
        if(!len[p].empty())
            maxd[prt[p]].insert(*len[p].begin());
        if(maxd[prt[p]].size()>1)
            all.insert(Export(maxd[prt[p]]));
    }
}

void DFS(int root,int prt,multiset& len){
    if(dis[root]!=0)
        len.insert(dis[root]);
    dis[root]=dis[prt]+1;
    for(Edge* i=head[root];i!=NULL;i=i->next)
        if(i->to!=prt&&!vis[i->to])
            DFS(i->to,root,len);
}

void Solve(int root){
    vis[root]=true;
    if(dis[root]!=0)
        len[root].insert(dis[root]);
    dis[root]=0;
    for(Edge* i=head[root];i!=NULL;i=i->next){
        if(!vis[i->to])
            DFS(i->to,root,len[root]);
    }
    maxd[root].insert(0);
    for(Edge* i=head[root];i!=NULL;i=i->next){
        if(!vis[i->to]){
            ::root=0;
            cursize=size[i->to];
            GetRoot(i->to,root);
            int son=::root;
            prt[son]=root;
            Solve(son);
            if(!len[son].empty())
                maxd[root].insert(*len[son].begin());
        }
    }
    if(maxd[root].size()>1)
        all.insert(Export(maxd[root]));
}

void GetRoot(int root,int prt){
    size[root]=1;
    msize[root]=0;
    for(Edge* i=head[root];i!=NULL;i=i->next){
        if(!vis[i->to]&&i->to!=prt){
            GetRoot(i->to,root);
            size[root]+=size[i->to];
            msize[root]=std::max(msize[root],size[i->to]);
        }
    }
    msize[root]=std::max(msize[root],cursize-size[root]);
    if(msize[root]<msize[::root])
        ::root=root;
}

inline void Insert(int from,int to){
    topE->from=from;
    topE->to=to;
    topE->next=head[from];
    head[from]=topE++;
}

void DFS(int root,int prt,int deep){
    size[root]=1;
    pprt[root]=prt;
    ::deep[root]=deep;
    for(Edge* i=head[root];i!=NULL;i=i->next){
        if(i->to!=prt){
            DFS(i->to,root,deep+1);
            size[root]+=size[i->to];
            if(size[i->to]>size[son[root]])
                son[root]=i->to;
        }
    }
}

void DFS(int root,int top){
    ::top[root]=top;
    if(son[root])
        DFS(son[root],top);
    for(Edge* i=head[root];i!=NULL;i=i->next)
        if(i->to!=pprt[root]&&i->to!=son[root])
            DFS(i->to,i->to);
}

inline int Dis(int x,int y){
    return deep[x]+deep[y]-2*(deep[LCA(x,y)]);
}

inline int LCA(int x,int y){
    while(top[x]!=top[y]){
        if(deep[top[x]]<deep[top[y]])
            std::swap(x,y);
        x=pprt[top[x]];
    }
    if(deep[x]>deep[y])
        std::swap(x,y);
    return x;
}

inline int ReadInt(){
    int x=0;
    register char ch=getchar();
    while(!isdigit(ch))
        ch=getchar();
    while(isdigit(ch)){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x;
}

inline char GetCmd(){
    register char ch=getchar();
    while(ch!='C'&&ch!='G')
        ch=getchar();
    return ch;
}

inline int Export(const multiset& s){
    auto it=s.begin();
    ++it;
    return *s.begin()+*it;
}