[SDOI2015]寻宝游戏 题解

自己搞出来一种树状数组+倍增的做法,A掉之后发现网上的题解都是平衡树。心里还是有点美滋滋。

于是决定分享出来。(其实只是想找个借口颓废一下)

不过其实非常简单,耐心读一读就懂了。

在阅读实现部分之前,请不要考虑“这个操作怎么实现呢?”“时间复杂度会不会过高?”这类的问题。否则很可能你会很快放弃阅读。先理解这种做法的流程即可。(可以先剧透一下:时间复杂度大约是O(m\,log^2n)

题意分析

分析一下题意,其实就是给定一棵树,在这棵树上选择某几个节点(设这几个节点的集合为S),求从其中的某个节点出发,经过所有被选择的节点后再回到出发点的最短路径长度。

从起点到终点,和从终点到起点的路径长度L是一样的,仅仅是沿原路返回而已。

也就是说,我们要求的即是将所有S中的节点连接起来的路径长度的二倍,即2L

下两图分别是S={3,4,6}时的路径和S={2,3}时的路径,请自行理解,我就不再赘述。

(在机房只能用Windows 7的画图工具,只能说还算能看吧)

那么,我们可以求出把选择的所有节点连接起来的最短路径,然后输出它的二倍。

于是题目就变成了,动态维护使树上某些节点连通的最短路径长度,并且在每一次修改操作完成后输出这个长度的二倍。

解决方案

题目中有两种操作,增加选择的节点和删除选择的节点。

假设要处理的节点为u,我们先考虑将向S中增加u的情况。删除u的情况是可以建立在增加u的情况之上的:令S'=S-{u},在S中删除u的花费就是在S'中增加u的花费——他们是前后两种路径长度的差。

现在考虑增加u时的情况。

情况1.|S|=0,即S中还没有任何节点。向其中加入u也不会产生任何长度。因此可以不修改答案。

情况2.在原图中,u至少有两个子节点(设其中一个为v) ,满足以v为根节点的子树中有节点属于S

于是u是属于S的2个(或更多)点的LCA,使他们连通则必须经过u。那么,在加入u之前,使节点连通的路径就已经经过了u,因此可以不修改答案。

如下图所示,4的两个子节点5,8的子树中都至少有一个节点在S中,在加入4之前,连通S中节点的路径就已经经过了4。即加入4也不会对答案造成影响。

情况3.在原图中,以u为根的子树中有节点属于S,并且以u为根的子树外也有节点属于S

那么同上,在加入u之前,使节点连通的路径已经经过了u。换句话说,u的加入不会对路径长度造成影响,因此不需要修改答案。

如图所示,假如要加入5,在加入5之前已有4,7 \in S,连接4,7的路已经覆盖了5,因此加入5不会使答案改变。

情况4.不满足上述三种情况中的任何一个。

那么我们需要找到一个在原路径上的点v,满足dist(u,v)最小。并且使答案加上dist(u,v)

寻找v的方法是,从u开始向上倍增,找到离u最近的,且子树中有节点属于S的点。设这个点为y

那么:

a.假如y在原有路径上,即加入u之前,y就被使节点连通的路径覆盖。也就是说,y满足情况2或情况3。

此时v=y

那么只需要让答案加上dist(u,y).

即,如下图所示:

u=9,S={3,4,7}4u 能到达的 最近的 子树中有节点在S中的 点。

那么只需要将94连接起来即可。

b.假如y不在原有路径上,那么以y的子树外一定没有节点在S中。(否则满足情况3,原有路径一定经过y

也就是说,S中的点全部都在以y为根的子树中。

我们只需要在这当中选择一个离u最近的点,将它与u连起来即可。

如下图所示:

那如何寻找离u最近的v呢?(请先往上翻,确认自己已知悉u,y,v的含义后再继续阅读)

dist(v,u)=dist(v,y)+dist(y,u)可知,无论选择哪个点,都有一段dist(y,u),而这段距离是已固定的。(当前只有v不确定)

所以我们要找的其实是dist(v,y)最小的点。

由于yv的父节点,所以有:

dist(root,v)=dist(root,y)+dist(v,y)

dist(root,y)是恒定的。

所以我们要找的就是dist(root,v)最小的点。

于是可以先处理出每个点到根节点(任选一个即可)的距离。

以上的讨论就包含所有的情况了。

代码实现

上述流程有几个需要高效算法维护的内容:

1.节点x的子树中有多少节点属于S

2.离节点x最近的 子树中有节点属于S的 点;

3.树上任意两点间的距离;

4.已经被路径覆盖的点中,距离根最近的点。

由于要维护子树中的信息,很自然地想到用DFS序。设In(x)表示深度优先搜索时,x是第几个被遍历到的。Out(x)表示从x往上回溯时,已经遍历了多少的点。

x的子树中的点就是DFS序在[In(x),Out(x)]中间的点。

当我们要将y加入到s中时,令FT[In(y)]=1。那么\sum_{i=In(x)}^{Out(x)}FT[i]就是以x为根的子树中在S中的个数。

用树状数组维护即可。

于是1就解决了。单次操作O(log\,n)

树上x,y之间的距离等于dist(root,x)+dist(root,y)-2*dist(root,LCA(x,y)),于是用LCA维护即可。巧了,我们本来就要维护每个节点的dist(root,x)啊,一举两得。

于是问题3解决。单次操作O(log\, n)

由于只要x的子树中有节点属于S,那么x的父节点(或者父节点的父节点,等等)中也一定有节点属于S。换句话说,”子树中是否有节点属于S“ 这一属性具有单调性。

于是可以用倍增的方法。每次向上倍增某个节点的2^k个祖先,找到最近的即可。

(又巧了,倍增LCA不正好维护了每个节点的2^k倍祖先么?)

于是问题2可在log^2n内解决。

最巧的是问题4。 由于树的形态确定后,每个点xdist(root,x)都是不变的,所以可以考虑小根堆维护。

但是,是不是我们要把路径上所有的点(包括没在S中的点)都加入小根堆?如果是,那么每次需要O(n\,logn)的时间来找出路径上的点并将其加入小根堆中。这显然是不可接受的。

重新考虑之前讨论的4种加入点的情况。除了在S中的点,我们只需要将距离根最近的点加入小根堆即可。

例如,在情况1(|S|=0 )中,我们将这唯一添加进去的点加入小根堆即可。

在情况2(有至少两个子树中有点属于S)中,我们将正在处理的u(即图中的4)加入小根堆即可。它就是最近的,最有可能被选中的点。

假如4在后面被删掉了怎么办?会不会遗漏5,8这种候选项?

不会。

假如4被删掉,我们先不在小根堆中删除4,而是在取用它的时候判断它是否在路径上。只要它在路径上(满足情况2或3或者本身就是S中的点),就直接取用,否则将它弹出,考虑下一个候选项。

如果4被弹出,那么除非有其它操作使得58在路径上,否则候选项肯定不可能是58

而当其它操作使得58在路径上并且可能成为备选点时,我们会将58加入小根堆,所以不会遗漏。

类似地,在情况3下,将要处理的点(图中的9)加入小根堆即可。

在情况4下,将倍增找到的点和正处理的点加入小根堆即可。

其实我们发现,除了要向上倍增的情况,所有情况都要将要处理的点加入小根堆中。

#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>

//#define LOC
#define nowy (L[i].to)
using std::queue;
using std::priority_queue;
template <typename T>
inline void read(T &x){
    x=0;char c; T f=1;
    do{c=getchar();if(c=='-')f=-1;}while(c>'9'||c<'0');
    do{x=x*10+c-'0';c=getchar();}while(c>='0'&&c<='9');x*=f;
}

const int N=1e5 + 10;

int n,m,t;
int h[N],tot=1;
int f[N][18];
int d[N];
long long len[N];
int bg[N],ed[N];
int Inq[N];
int DFN;
int TotIn;
int Diff[N];//Diff是FT的一个拷贝 便于直接确认一个点是否在S中
int x,y,z;
int Num_SonIn,Cls_F;
long long ans=0;

struct line{
    int to,nxt,w;
}L[2*N];

struct OneNode{
    int num;
    bool operator <(const OneNode b)const {
        if(len[num]==len[b.num])return d[num]>d[b.num];
        return len[num]>len[b.num];
    }
    OneNode(int x):num(x){}
};//通过便于维护小根堆
struct FenwickTree{
    int v[N];
    inline void clear(){
        memset(v,0,sizeof(v));
    }
    inline void add(int x,int y){
        for(;x<=n;x+=x&-x){
            v[x]+=y;
        }
    }
    inline int ask(int x){
        int res=0;
        while(x>0){
            res+=v[x];
            x-=x&-x;
        }
        return res;
    }
    FenwickTree(){clear();}
}FT;
priority_queue<OneNode> OQ;

inline void add(int x,int y,int z){
    L[++tot].to=y;L[tot].nxt=h[x];h[x]=tot;L[tot].w=z;
    L[++tot].to=x;L[tot].nxt=h[y];h[y]=tot;L[tot].w=z;
}

void GetLCA_DFS(int x){
//DFS 同时求出祖先数组、距离根节点的距离、DFS序
    bg[x]=++DFN;
    for(int i=h[x];i;i=L[i].nxt){
        if(d[nowy])continue;
        d[nowy]=d[x]+1;
        f[nowy][0]=x;
        len[nowy]=len[x]+L[i].w;
        for(int j=1;j<=t;++j){
            f[nowy][j]=f[f[nowy][j-1]][j-1];
        }
        GetLCA_DFS(nowy);
    }
    ed[x]=DFN;
}
inline int LCA(int x,int y){
    if(d[x]>d[y]){
        x^=y;y^=x;x^=y;
    }
    //d[x]<=d[y]
    for(register int i=t;i>=0;--i){
        if(d[f[y][i]]>=d[x]){
            y=f[y][i];
        }
    }
    if(x==y)return x;
    for(register int i=t;i>=0;--i){
        if(f[y][i]!=f[x][i]){
            y=f[y][i];
            x=f[x][i];
        }
    }
    return f[x][0];
}
inline long long LEN(int x,int y){
    return 1ll*len[x]+len[y]-2*len[LCA(x,y)];
}
inline int GetSonIn(int x){//including x
//判断x的子树中有多少节点属于S
    if(!x)return TotIn;
    int Num=FT.ask(ed[x])-FT.ask(bg[x]-1);
    return Num;
}
inline bool TwoSon(int x,int v){
//是否满足情况2
    int SonV;
    for(register int i=h[x];i;i=L[i].nxt){
        if(d[nowy]<=d[x])continue;
        SonV=GetSonIn(nowy);

        if(SonV){
            if(SonV==v)return false;
            return true;
        }
    }
    return false;
}
inline bool check(int x){
//是否满足情况2或3 这两种情况可以一同处理
    if(!x)return true;
    int Num_SonIn;
    return (Num_SonIn=GetSonIn(x))&&(Num_SonIn<TotIn||TwoSon(x,Num_SonIn));
}
inline int GetCls_F(int x){
//倍增求离自己最近的 子树里有节点属于S 的节点
    if(GetSonIn(x))return x;
    int Num;
    for(register int i=t;i>=0;--i){
        if(!(Num=GetSonIn(f[x][i]))){
            x=f[x][i];
        }
    }
    return f[x][0];
}
inline void Change(long long t){
//通过t变量实现增加删除在同一个函数处理 减少码量
    if(TotIn!=0){
        if(!check(x)){
            Cls_F=GetCls_F(x);
            if(check(Cls_F)){
                if(t&&!Inq[Cls_F]){OQ.push(OneNode(Cls_F));Inq[Cls_F]=1;}
                    ans+=LEN(x,Cls_F)*(-1+2*t);
            }
            else {
                while(!OQ.empty()){
                    z=OQ.top().num;
                    if(check(z)||Diff[z])break;
                    OQ.pop();
                    Inq[z]=0;
                }
                if(t&&!Inq[Cls_F]){OQ.push(OneNode(Cls_F));Inq[Cls_F]=1;}
                ans+=LEN(x,z)*(-1+2*t);
            }
        }
    }
}
int main(){
    read(n);read(m);
    t=log(n)/log(2)+1;
    for(register int i=1;i<n;++i){
        read(x);
        read(y);
        read(z);
        add(x,y,z);
    }
    d[1]=1;
    GetLCA_DFS(1);
    for(register int i=1;i<=m;++i){
        read(x);
        if(!Diff[x]){
            Change(1);
            FT.add(bg[x],1);
            Diff[x]+=1;
            if(!Inq[x]){Inq[x]=1;OQ.push(OneNode(x));}
            ++TotIn;
        }
        else{
            --TotIn;
            FT.add(bg[x],-1);
            Diff[x]-=1;

            Change(0);
        }
        printf("%lld\n",ans*2);
    }
    return 0;
}

然后就可以愉快地AC了。

Uae牛逼!

留下评论

您的电子邮箱地址不会被公开。