[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}$ ， $4$ 是 $u$ 能到达的最近的子树中有节点在 $S$ 中的点。

那么只需要将 $9$ 与 $4$ 连接起来即可。

$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)$ 最小的点。

由于 $y$ 是 $v$ 的父节点，所以有：

$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。 由于树的形态确定后，每个点 $x$ 的 $dist(root,x)$ 都是不变的，所以可以考虑小根堆维护。

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

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

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

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

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

不会。

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

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

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

类似地，在情况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牛逼！

[SDOI2015]寻宝游戏题解

题意分析

解决方案

代码实现

留下评论

取消回复