[AHOI2005] 航线规划

Description

给定一张图，需要支持两个操作：

• 查询 $u,v$ 两点间的必经边数量。
• 删除 $u,v$ 直接相连的边，保证一定存在。

$n\leq 3\times 10^4,m\leq 10^5,q\leq 4\times 10^4$

Solution

首先可以发现题目本质是要求动态维护边双树，边双树上的删边操作并不好处理，我们将询问离线下来转化为加边操作，这样可以通过缩点在上限为 $\mathcal{O}(n)$ 的时间内维护树的形态。
假如我们已经构建出来了边双树，那么 $u,v$ 两点间的必经边数量就是两点在边双树上的距离。
我们可以方便地在 LCT 上动态维护两点的距离，于是可以用 LCT 来维护边双树。

Code

int Find(int x){return x==uni[x]?x:uni[x]=Find(uni[x]);}
namespace LCT{
#define lc(x) c[x][0]
#define rc(x) c[x][1]
    int s[N],sz[N],fa[N],rev[N],c[N][2];
    bool isrt(int x){
        return fa[x]==0 || (lc(fa[x])!=x&&rc(fa[x])!=x);
    }
    void update(int x){
        sz[x]=sz[lc(x)]+sz[rc(x)]+1;
    }
    void revers(int x){
        swap(lc(x),rc(x));rev[x]^=1;
    }
    void pushdn(int x){
        if(rev[x]==0) return;
        revers(lc(x));revers(rc(x));
        rev[x]=0;
    }
    void rotate(int x){
        int y=fa[x],z=fa[y],t=rc(y)==x;
        if(!isrt(y)) c[z][rc(z)==y]=x;fa[x]=z;
        c[y][t]=c[x][t^1];fa[c[x][t^1]]=y;
        c[x][t^1]=y;fa[y]=x;
        update(y),update(x);
    }
    void splay(int x){
        int top,y=x;s[top=1]=x;
        while(!isrt(y)) y=fa[y],s[++top]=y;
        while(top) pushdn(s[top--]);
        while(!isrt(x)){
            int y=fa[x],z=fa[y];
            if(!isrt(y))
                ((rc(y)==x)^(rc(z)==y))?rotate(x):rotate(y);
            rotate(x);
        }
    }
    void access(int x){
        for(int i=0;x;x=fa[i=x]=Find(fa[x]))   //可能父节点已经被缩了
            splay(x),rc(x)=i,update(x);
    }
    void makert(int x){
        access(x),splay(x),revers(x);
    }
    int  findrt(int x){
        access(x);splay(x);
        while(lc(x)) 
            pushdn(x=lc(x));
        splay(x);
        return x;
    }
    void split(int x,int y){
        makert(x),access(y),splay(y);
    }
    void del(int x,int y){          // 缩点操作
        uni[x]=y;
        if(lc(x)) del(lc(x),y);
        if(rc(x)) del(rc(x),y);
    }
    void merge(int x,int y){
        if(x==y) return;
        makert(x);
        if(findrt(y)!=x)
            return fa[x]=y,void();
        del(rc(x),x);rc(x)=0;update(x);
    }
}
using namespace LCT;