长链剖分

luckydrawbox · 2024-01-08 14:38:44 · 个人记录

变量

函数

代码

struct LCD{
    int dep[N],mxd[N],Log[N],fa[N][21],son[N],top[N];
    vector<int>up[N],dn[N];
    void dfs1(int x){
        dep[x]=mxd[x]=dep[fa[x][0]]+1;
        for(int i=1;i<=19;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
        son[x]=-1;
        for(int i=0;i<e[x].size();i++){
            int y=e[x][i];
            if(y==fa[x][0])continue;
            dfs1(y);
            mxd[x]=max(mxd[x],mxd[y]);
            if(son[x]==-1||mxd[y]>mxd[son[x]])
                son[x]=y;
        }
    }
    void dfs2(int x,int q){
        top[x]=q;
        if(x==q){
            for(int i=0,f=x;i<=mxd[x]-dep[x];i++)
                up[x].push_back(f),f=fa[f][0];
            for(int i=0,f=x;i<=mxd[x]-dep[x];i++)
                dn[x].push_back(f),f=son[f];
        }
        if(son[x])dfs2(son[x],q);
        for(int i=0;i<e[x].size();i++){
            int y=e[x][i];
            if(y==son[x]||y==fa[x][0])continue;
            dfs2(y,y);
        }
    }
    int ask(int x,int k){
        if(!k)return x;
        x=fa[x][Log[k]];
        k-=(1<<Log[k]);
        k-=(dep[x]-dep[top[x]]);
        x=top[x];
        return k>=0?up[x][k]:dn[x][-k];
    }
    void init(int rt,int n){
        Log[0]=-1;
        for(int i=1;i<=n;i++)Log[i]=Log[i>>1]+1;
        dfs1(rt);dfs2(rt,rt);
    }
}lcd;