[BZOJ1095/Luogu2056][ZJOI2007]Hide 捉迷藏(动态点分治,堆)

发布于 2018-03-27  76 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1095/Luogu2056][ZJOI2007]Hide 捉迷藏(动态点分治,堆)

Description

捉迷藏 Jiajia和Wind是一对恩爱的夫妻,并且他们有很多孩子。某天,Jiajia、Wind和孩子们决定在家里玩捉迷藏游戏。他们的家很大且构造很奇特,由N个屋子和N-1条双向走廊组成,这N-1条走廊的分布使得任意两个屋子都互相可达。游戏是这样进行的,孩子们负责躲藏,Jiajia负责找,而Wind负责操纵这N个屋子的灯。在起初的时候,所有的灯都没有被打开。每一次,孩子们只会躲藏在没有开灯的房间中,但是为了增加刺激性,孩子们会要求打开某个房间的电灯或者关闭某个房间的电灯。为了评估某一次游戏的复杂性,Jiajia希望知道可能的最远的两个孩子的距离(即最远的两个关灯房间的距离)。 我们将以如下形式定义每一种操作: C(hange) i 改变第i个房间的照明状态,若原来打开,则关闭;若原来关闭,则打开。 G(ame) 开始一次游戏,查询最远的两个关灯房间的
距离。

Tag

动态点分治,堆

题目大意

动态维护图中最远的两个黑点的距离

解决思路

如果没有多次询问,我们用一遍点分治即可解决,具体来说分治每一个重心,要求这一次求出的答案一定要经过当前重心,那么枚举子树dfs求出点到当前重心的距离,用两棵不同子树的最大值相加即为答案。最后从所有的分治重心取最大值。
但是,由于有对点的黑白状态的改变,而我们不能每一次都分治求一遍。考虑到每一次只会改变一个点,那么对应到我们分治的过程,只会有logn个地方的转移是不同的,那么我们可以动态点分治。
在开始的时候先走一遍点分治过程,将每一个重心与它下一层分治出的重心相连,这样可以构出一棵点分树。由点分治的性质可以得到点分树的高度是\(logn\)的。
接下来考虑对于每一个重心要维护些什么。直接点分治求的方式启发我们每一个重心的答案与到这个重心的不同子树内的两个最大值有关。所以我们对每一个点维护两个堆,一个堆维护这个重心u管辖的范围内的所有点到这个重心在点分树中的父亲。注意是这个重心的父亲。第二个堆维护这个重心在点分树中所有儿子的第一个堆的对顶。
为什么要这样维护呢?如果我们对每一个点只维护一个堆,在这个堆中存其管辖范围内所有点到它的距离,那么我们在得到最大和次大的时候不能保证是从不同的子树得到的,而必须是不同的子树得到的答案才会一定经过当前分治重心。所以,我们维护两个堆,一个堆维护辖区内点到重心的父亲的距离,再让另一个维护其点分树儿子的堆顶,那么第二个堆的最大值和次大值就可以保证是从不同的儿子处得到的了。
我们在全局再维护一个全局答案堆,这个堆存所有第二类堆的最大值+次大值之和。
然后我们考虑修改一个点的黑白属性,那么就从这个点所在的点分树一直向上跳,一边跳一遍改变三个堆的值,注意顺序。
至于两点距离的计算,可以用树链剖分或倍增,这里采用倍增的方式。
另外要注意的是,当我们关闭某一个点的灯时,这时是会有链的情况的,所以我们需要在对应的堆中加入一个0;反之,在关掉一个灯的时候,要在堆中删除一个0;。堆中任意元素的删除可以用一个删除堆来维护。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=200110;
const int maxM=maxN*2;
const int maxBit=20;
const int inf=214748367;

class Heap//自己写一个支持删除任意元素的堆
{
public:
    priority_queue<int> Q1,Q2;
    void Update(){//实时更新
        while ((!Q2.empty())&&(Q1.top()==Q2.top())) Q1.pop(),Q2.pop();
    }
    int Size(){
        return Q1.size()-Q2.size();
    }
    void Insert(const int x){
        Q1.push(x);
    }
    void Delete(const int x){
        Q2.push(x);
    }
    bool Empty(){
        Update();return Q1.empty();
    }
    void Pop(){
        Update();Q1.pop();
    }
    int Top(){
        Update();return Q1.top();
    }
    int STop(){//得到第二大的值,注意要提前判断是否存在第二大
        int x=Top();Pop();
        int ret=Top();Insert(x);
        return ret;
    }
};

int n;
int edgecnt=0,Head[maxN],Next[maxM],V[maxM];
int Size[maxN],Depth[maxN],ST[maxN][maxBit+1];
int root,mxSon[maxN],nowsum;
bool vis[maxN];
int offcnt=0,Fa[maxN];
Heap H1[maxN],H2[maxN],Ans;
bool Status[maxN];

void Add_Edge(int u,int v);
void dfs_ST(int u,int fa);
int Dist(int u,int v);
void GetRoot(int u,int fa);
void Div(int u);
void Insert_Ans(int u);
void Delete_Ans(int u);
void Off(int u);
void On(int u);

int main()
{
    mem(Head,-1);

    scanf("%d",&n);
    for (int i=1;i<n;i++)
    {
        int u,v;scanf("%d%d",&u,&v);
        Add_Edge(u,v);Add_Edge(v,u);
    }

    Depth[1]=1;//dfs求出倍增求lca时需要的祖先数组
    dfs_ST(1,1);
    for (int i=1;i<=maxBit;i++)//构造倍增
        for (int j=1;j<=n;j++)
            if (ST[j][i-1])
            ST[j][i]=ST[ST[j][i-1]][i-1];

    nowsum=n;mxSon[0]=inf;root=0;//建立点分树
    GetRoot(1,1);Fa[root]=0;
    Div(root);

    for (int i=1;i<=n;i++) Off(i);//开始时全部初始化为关闭

    int m;scanf("%d",&m);
    while (m--)
    {
        char opt[5];scanf("%s",opt);
        if (opt[0]=='G')//查询
            if (offcnt==1) printf("0\n");
            else if (offcnt==0) printf("-1\n");
            else printf("%d\n",Ans.Top());
        if (opt[0]=='C')//修改
        {
            int u;scanf("%d",&u);
            if (Status[u]==0) On(u);
            else Off(u);
        }
    }
    return 0;
}

void Add_Edge(int u,int v)
{
    edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;V[edgecnt]=v;
    return;
}

void dfs_ST(int u,int fa)//dfs求父亲
{
    for (int i=Head[u];i!=-1;i=Next[i])
        if (V[i]!=fa)
        {
            Depth[V[i]]=Depth[u]+1;ST[V[i]][0]=u;
            dfs_ST(V[i],u);
        }
    return;
}

int Dist(int u,int v)//倍增求两点之间的距离
{
    int ret=Depth[u]+Depth[v];
    if (Depth[u]<Depth[v]) swap(u,v);
    for (int i=maxBit;i>=0;i--)
        if ((ST[u][i]!=0)&&(Depth[ST[u][i]]>=Depth[v])) u=ST[u][i];
    if (u==v) return ret-2*Depth[u];
    for (int i=maxBit;i>=0;i--)
        if ((ST[u][i]!=0)&&(ST[v][i]!=0)&&(ST[u][i]!=ST[v][i])) u=ST[u][i],v=ST[v][i];
    u=ST[u][0];
    return ret-2*Depth[u];
}

void GetRoot(int u,int fa)//得到当前子树的重心
{
    Size[u]=1;mxSon[u]=0;
    for (int i=Head[u];i!=-1;i=Next[i])
        if ((V[i]!=fa)&&(vis[V[i]]==0))
        {
            GetRoot(V[i],u);Size[u]+=Size[V[i]];
            mxSon[u]=max(mxSon[u],Size[V[i]]);
        }
    mxSon[u]=max(mxSon[u],nowsum-Size[u]);
    if (mxSon[u]<mxSon[root]) root=u;
    return;
}

void Div(int u)//点分治,勾出构出点分树
{
    vis[u]=1;
    for (int i=Head[u];i!=-1;i=Next[i])
        if (vis[V[i]]==0)
        {
            root=0;nowsum=Size[V[i]];
            GetRoot(V[i],V[i]);Fa[root]=u;
            Div(root);
        }
    return;
}

void Insert_Ans(int u)//把u点的答案加入答案堆
{//注意需要判断u的堆是否有两个元素
    if (H2[u].Size()>=2) Ans.Insert(H2[u].Top()+H2[u].STop());
    return;
}

void Delete_Ans(int u)//把u的答案从答案堆中删除
{
    if (H2[u].Size()>=2) Ans.Delete(H2[u].Top()+H2[u].STop());
    return;
}

void Off(int u)//把u点灯关掉
{
    offcnt++;Status[u]=0;
    Delete_Ans(u);//先把u的答案删掉
    H2[u].Insert(0);//u开了之后,可能会有链的答案,所以要加入一个0
    Insert_Ans(u);//更新答案

    int now=u;
    while (Fa[now])//向上跳点分树
    {
        Delete_Ans(Fa[now]);//首先把父亲的答案去除

        if (!H1[now].Empty()) H2[Fa[now]].Delete(H1[now].Top());//把原来的堆顶删掉
        H1[now].Insert(Dist(u,Fa[now]));//加入新的元素
        H2[Fa[now]].Insert(H1[now].Top());//再把堆顶加入父亲的堆

        Insert_Ans(Fa[now]);//重新加入答案
        now=Fa[now];
    }
    return;
}

void On(int u)//把u节点打开,可以类比关闭
{
    offcnt--;Status[u]=1;
    Delete_Ans(u);
    H2[u].Delete(0);
    Insert_Ans(u);

    int now=u;
    while (Fa[now])
    {
        Delete_Ans(Fa[now]);

        H2[Fa[now]].Delete(H1[now].Top());
        H1[now].Delete(Dist(u,Fa[now]));
        if (!H1[now].Empty()) H2[Fa[now]].Insert(H1[now].Top());
        Insert_Ans(Fa[now]);
        now=Fa[now];
    }
    return;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1095/Luogu2056][ZJOI2007]Hide 捉迷藏(动态点分治,堆)


HNCJ OIer