题解：P10658 BZOJ2959 长跑

· · 题解

算是一道 LCT 维护边双连通分量的模板题，如果可以理解 P10657 的话这道题就十分 easy 了。

LCT 维护边双连通分量

先讲一下这个知识点。

思想

正常情况下 LCT 维护的是一个森林结构，也就是不知道多少棵树，因为没有删边操作，所以我们可以考虑把一个边双连通分量缩成一个点。

显然不可能让你跑 tarjan 因为有动态加边操作，那怎么 LCT 上缩点呢？其实是可以用并查集的呀，每次找到环把环上每个点并到一起不就好了。

代码实现

在大脑里翻一下 LCT 的基础操作，其实大部分代码没有涉及到森林的维护，这些代码是完全不需要动的，直接套板子就可以。

而这两个函数是需要改的：

void access(int x){
    ...
}
void link(int x,int y){
    ...
}

那我们思考一下怎么改。

先来考虑 link 操作，既然用了并查集，那是不是就会需要先找到 x,y 分别属于哪个集合呢？那如果 x,y 本来就在一起显然就不需要连边，否则的话，如果连完边会出现一个环也就是连边之前 x,y 是连通的，那就需要合并两个并查集。

想想怎么合并，因为你在 LCT 上查 x,y 是否连通的时候已经打通了一条 x 到 y 的实链，所以这个时候直接把实链上所有的点缩到一起就可以了，假设此时该实链的 splay 树中根节点是 x，那么直接从 x 的右子开始，把整棵树压到 x 上就好了，代码如下。

void merge(int x,int rt){
    f[x]=rt;//合并并查集

    t[rt].cnt+=t[x].cnt;
  //这个是这道题要用的，和现在讲的东西无关，当然，如果需要知道并查集中点的个数，那还是需要一句类似的代码来实现的

  if(ls(x))merge(ls(x),rt);
    if(rs(x))merge(rs(x),rt);
}
void link(int x,int y){
    x=find(x);y=find(y);
    if(x==y)return;
    evert(x);
    if(findroot(y)!=x)fa(x)=y;
    else merge(rs(x),x),rs(x)=0,up(x);
}

注意要把 x 的右子赋成 0，因为要把原本那些点全都丢掉，也正是因为把后面用不到的点丢掉了，所以并查集合并的部分不需要查这个点在哪个集合。

搞明白这个之后 access 就很好改了，因为要把没用的点丢掉，所以每次都要用 x 所在并查集的头做当前 splay 上去的 x，然后还要把 x 在 LCT 上的父节点信息也改掉，具体代码如下。

void access(int x){
    x=find(x);
    for(int y=0;x;x=fa(y=x)){
        splay(x);
        rs(x)=y;
        up(x);
        fa(x)=find(fa(x));//既要改x，又要改fa(x)，加在一起其实只需要这一句
    }
}

好的，你现在已经会用 LCT 维护边双连通分量了。

对于本题单独的分析

与 P10657 不同的是，这道题还需要维护点权和信息，当然，这个还是非常好维护的，用过 LCT 的宝宝们应该都会。

然后就是这道题有修改点权的操作，因为我们把它的点权丢给了并查集的头，所以需要让这个头加一个差值，然后修改一下变量。

其余的就没什么了，直接看代码吧。

代码实现

struct lct{
    ll cnt,sum;
    int fa,ch[2];
    bool tag;
}t[N];
#define fa(x) t[x].fa
#define ls(x) t[x].ch[0]
#define rs(x) t[x].ch[1]
void up(int x){
    t[x].sum=t[ls(x)].sum+t[x].cnt+t[rs(x)].sum;
}
void reverse(int x){
    swap(ls(x),rs(x));
    t[x].tag^=1;
}
void down(int x){
    if(t[x].tag){
        reverse(ls(x));
        reverse(rs(x));
        t[x].tag=0;
    }
}
bool notroot(int x){
    return ls(fa(x))==x or rs(fa(x))==x;
}
void push(int x){
    if(notroot(x))push(fa(x));
    down(x);
}
bool ident(int x,int f){
    return rs(f)==x;
}
void connect(int x,int f,bool k){
    t[fa(x)=f].ch[k]=x;
}
void rotate(int x){
    int f=fa(x),g=fa(f);bool k=ident(x,f);
    connect(t[x].ch[k^1],f,k);
    fa(x)=g;
    if(notroot(f))t[g].ch[ident(f,g)]=x;
    connect(f,x,k^1);
    up(f);up(x);
}
void splay(int x){
    push(x);
    while(notroot(x)){
        int f=fa(x),g=fa(f);
        if(notroot(f))ident(x,f)^ident(f,g)?rotate(x):rotate(f);
        rotate(x);
    }
}

//上面和正常的LCT没有任何区别

int f[N];//并查集
int find(int x){
    return f[x]==x?x:f[x]=find(f[x]);
}

void access(int x){
    x=find(x);
    for(int y=0;x;x=fa(y=x)){
        splay(x);
        rs(x)=y;
        up(x);
        fa(x)=find(fa(x));
    }
}
void evert(int x){
    access(x);
    splay(x);
    reverse(x);
}
int findroot(int x){
    access(x);
    splay(x);
    while(ls(x))x=ls(x);
    splay(x);
    return x;
}
void merge(int x,int rt){
    f[x]=rt;
    t[rt].cnt+=t[x].cnt;
    if(ls(x))merge(ls(x),rt);
    if(rs(x))merge(rs(x),rt);
}
void link(int x,int y){
    x=find(x);y=find(y);
    if(x==y)return;
    evert(x);
    if(findroot(y)!=x)fa(x)=y;
    else merge(rs(x),x),rs(x)=0,up(x);
}
void split(int x,int y){
    evert(x);
    access(y);
    splay(y);
}

int n, m;
ll val[N];

int main() {
    n = read();m = read();
    for(int i=1;i<=n;i++)t[f[i]=i].cnt=val[i]=read(),up(i);
    for(int i=1,opt,x,y;i<=m;i++){
        opt=read();x=read();y=read();
        if(opt==1)link(x,y);
        else if(opt==2){
            splay(find(x));
            t[find(x)].cnt+=y-val[x];
            val[x]=y;
            up(find(x));
        }
        else {
            x=find(x);y=find(y);
            evert(x);
            if(findroot(y)!=x)write(-1);
            else split(x,y),write(t[y].sum);
        }
    }
    return 0;
}

实话说，一开始 opt==2 那里少写了一个 splay，debug 半天也没找出来，然后一气之下就去睡觉了（尬笑挠头）。