题解：P14486 [集训队互测 2018] 北校门外的未来

· · 题解

重构树

既然题目里新加入的点编号是单调递增的，那我们不妨换个思路，尝试以“编号最大的点”为核心来重构这棵树 T'。具体怎么做呢？找出当前树中最大的点作为根节点，把它分离出来后，原树就会被自然切分成几个连通块。接着，我们再像套娃一样，递归地把每个连通块里的最大点与上一层的根相连就行啦。

在这棵新鲜出炉的重构树 T' 下，原图原本让人头疼的复杂跳跃规则瞬间被简化了。你稍微推导一下就会发现，在 T' 中，一个点能进行的最优或最长效的跳跃，必定是直接跳向它的某个祖先！而且，跳跃合法的条件也变得超级直观：如果点 x 想一跃跳到祖先 y，那么在原树中，x 到 y 路径上紧挨着 y 的那个点 z，必须在 T' 中待在 x 的子树内。

转化为贪心

既然明确了只能往祖先跳，那查询两个点 x 和 y 之间的最短步数这件麻烦事，其实就可以转化为：让 x 和 y 都在重构树上，向它们的最近公共祖先（LCA）进行贪心跳跃。

这里的贪心策略很简单：首先贪心地往深度最浅的合法节点跳，直到再跳一步就会越过 LCA 为止。假设在这个临界状态下，两边合计跳了 c 步。此时它们离胜利会师真的就只差一捏捏了！我们只需要在 LCA 附近进行一下简单的分类讨论：

为什么必须用 LCT 维护？

如果这道题是静态的，那我们直接建出 T' 跑个倍增就能轻松 AC 了。但出题人显然没打算让我们这么好过——题目是动态加点的！每次加入的新点都是当前最大的点，这会导致重构树的形态以及跳跃的前驱和后继关系不断发生变化。

没办法，遇到这种动态树问题，只能请出神秘的 LCT 来动态维护这棵重构树了。在 LCT 的辅助图上，我们可以把边分为代表直接连通的“实边”，以及代表当前辅助图同父节点的“虚边”。其实 LCT 中的 Access 操作，在这里的本质就是在这棵动态树上提取出这种“贪心跳跃”的极长连通块（也就是实边链）。查询的时候，只要从 x 和 y 分别 Access 到 LCA 取出跳跃的权值，再结合上面提到的 c+2 或 c+3 的端点判断（对应代码中的 gfir 函数），就能顺利得到最终的最短步数啦！

代码实现


#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,m,tt,tt2,cn,op[N*5],rx[N*5],ry[N*5];
int ls[N],to[N<<1],nx[N<<1],h[N],to2[N],nx2[N];
int pos[N],fa[N],dwn[N],low[N],sz[N],dep[N];
int son[N],tp[N],rfn[N],ed[N],sk[N],skp;
int dsu[N];

void add(int x,int y){to[++tt]=y;nx[tt]=ls[x];ls[x]=tt;}
void add2(int x,int y){to2[++tt2]=y;nx2[tt2]=h[x];h[x]=tt2;}
int F(int x){return dsu[x]==x?x:dsu[x]=F(dsu[x]);}

void dfs1(int x){
    while(skp&&pos[sk[skp]]>pos[x])dwn[sk[skp--]]=x;
    sk[++skp]=x;sz[x]=1;
    for(int i=h[x];i;i=nx2[i]){
        int y=to2[i];
        fa[y]=x;dep[y]=dep[x]+1;
        dfs1(y);sz[x]+=sz[y];
        if(sz[y]>sz[son[x]])son[x]=y;
    }
}
void dfs2(int x){
    rfn[x]=++cn;
    if(son[x]){tp[son[x]]=tp[x];dfs2(son[x]);}
    for(int i=h[x];i;i=nx2[i]){
        int y=to2[i];
        if(y==son[x])continue;
        tp[y]=y;dfs2(y);
    }
    ed[x]=cn;
}
int lca(int x,int y){
    while(tp[x]!=tp[y]){
        if(dep[tp[x]]<dep[tp[y]])swap(x,y);
        x=fa[tp[x]];
    }
    return dep[x]<dep[y]?x:y;
}
int gtp(int x,int y){
    while(tp[x]!=tp[y]){
        if(fa[tp[x]]==y)return tp[x];
        x=fa[tp[x]];
    }
    return son[y];
}
bool gfir(int x,int y){
    int z=gtp(x,y);
    return rfn[x]<=rfn[low[z]]&&rfn[low[z]]<=ed[x];
}

struct LCT{
    int t[N][2],f[N],cf[N],w[N],c[N],sn[N];
    bool nr(int x){return f[x]&&(t[f[x]][0]==x||t[f[x]][1]==x);}
    bool dir(int x){return t[f[x]][1]==x;}
    void up(int x){w[x]=w[t[x][0]]+w[t[x][1]]+c[x];}
    void rot(int x){
        int y=f[x],z=f[y],xs=dir(x),ys=dir(y),W=t[x][xs^1];
        if(nr(y))t[z][ys]=x;
        t[y][xs]=W;t[x][xs^1]=y;
        if(W)f[W]=y;
        f[y]=x;f[x]=z;
        up(y);up(x);
    }
    void splay(int x){
        while(nr(x)){
            int y=f[x];
            if(!nr(y))rot(x);
            else if(dir(x)==dir(y))rot(y),rot(x);
            else rot(x),rot(x);
        }
    }
    void acc(int x){
        for(int y=0;x;y=x,x=f[x])splay(x),t[x][1]=y,up(x);
    }
    int mktp(int x){
        splay(x);
        if(!t[x][0])return f[x];
        x=t[x][0];
        while(t[x][1])x=t[x][1];
        splay(x);t[x][1]=0;up(x);
        return x;
    }
    void mdf(int x,int W){splay(x);c[x]=W;up(x);}
    int getT(int x){splay(x);while(t[x][0])x=t[x][0];return x;}
    int getB(int x){splay(x);while(t[x][1])x=t[x][1];return x;}
    void ins(int x,int y){
        if(x>y){f[y]=cf[y]=x;c[y]=w[y]=1;return;}
        int u,v=dwn[y];u=mktp(v);
        mdf(y,c[v]);mdf(v,!u);
        f[y]=u;f[v]=y;
        if(sn[u]==v)sn[u]=y;
        if(u)sn[y]=v;
        int z=0,nw=0,lw=x;
        while(x){
            splay(x);t[x][1]=z;up(x);
            if(w[x]){
                while(x){
                    if(w[t[x][1]])x=t[x][1];
                    else if(c[x])break;
                    else x=t[x][0];
                }
                if(x>y)break;
                u=mktp(x);
                if(u>y)break;
                splay(lw);t[lw][1]=0;
                if(sn[lw]){
                    splay(sn[lw]);f[sn[lw]]=u;mdf(sn[lw],1);sn[lw]=0;
                }
                int pre=cf[x];mdf(x,0);
                x=getB(x);splay(x);
                if(nw)f[nw]=x,sn[x]=t[x][1]=getT(nw);
                nw=x;z=0;lw=x=pre;
            }else z=x,x=f[x];
        }
        cf[y]=cf[dwn[y]];cf[dwn[y]]=y;
        if(nw)nw=getT(nw),mdf(nw,1),f[nw]=y;
    }
    pair<int,int> ask(int x,int y){
        if(x==y)return {0,0};
        acc(x);splay(x);
        int dis=0,top=0,pre=x;
        while(x){
            if(x<y)top=x,x=t[x][0];
            else x=t[x][1];
        }
        splay(top);x=t[top][1];
        if(!w[x])return {0,pre};
        dis=w[x];
        while(x){
            if(w[t[x][0]])x=t[x][0];
            else if(c[x]){
                if(t[x][0]){
                    x=t[x][0];
                    while(t[x][1])x=t[x][1];
                    return {dis,x};
                }
                return {dis,top};
            }else top=x,x=t[x][1];
        }
        return {dis,top};
    }
    int qry(int x,int y){
        if(x==y)return 0;
        if(x>y)swap(x,y);
        int la=lca(x,y);
        if(la==y){
            pair<int,int> A=ask(x,y);
            int ans=A.first+2;
            if(gfir(A.second,y))ans--;
            return ans;
        }
        pair<int,int> A=ask(x,la),B=ask(y,la);
        int ans=A.first+B.first+3;
        if(gfir(A.second,la)&&gfir(B.second,la))ans--;
        return ans;
    }
}T;

int main(){
    scanf("%d%d",&n,&m);
    n=1;
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&op[i],&rx[i],&ry[i]);
        n=max(n,ry[i]);
        if(op[i]==1){
            add(rx[i],ry[i]);
            add(ry[i],rx[i]);
            pos[ry[i]]=i;
        }
    }
    for(int i=1;i<=n;++i)dsu[i]=i;
    for(int x=1;x<=n;++x){
        for(int i=ls[x];i;i=nx[i]){
            int y=to[i];
            if(F(y)<x){
                add2(x,F(y));
                dsu[F(y)]=x;
            }
        }
    }
    fa[n]=0;dep[n]=1;
    dfs1(n);tp[n]=n;dfs2(n);
    for(int x=1;x<=n;++x){
        for(int i=ls[x];i;i=nx[i]){
            int y=to[i];
            if(x>y)low[gtp(y,x)]=y;
        }
    }
    for(int i=1;i<=m;++i){
        if(op[i]==1)T.ins(rx[i],ry[i]);
        else printf("%d\n",T.qry(rx[i],ry[i]));
    }
    return 0;
}