bzoj 1023: [SHOI2008]cactus仙人掌图 2125: 最短路 4728: 挪威的森林 静态仙人掌上路径长度的维护系列

时间：2024-08-11 11:06:26

%%% http://immortalco.blog.uoj.ac/blog/1955

一个通用的写法是建树，对每个环建一个新点，去掉环上的边，原先环上每个点到新点连边，边权为点到环根的最短/长路长度

1023 求仙人掌直径

树形dp，维护每个点向下的最长和次长路径长度，对原有的点直接更新答案，对新点可以把对应环上的点取出，倍长，破环成链，并用单调队列正反各扫一次

#include<cstdio>

char buf[],*ptr=buf-;

int _(){

    int x=,c=*++ptr;

    while(c<)c=*++ptr;

    while(c>)x=x*+c-,c=*++ptr;

    return x;

}

const int N=;

int es[N],enx[N],ev[N],e0[N],e1[N],ep=;

int dfn[N],low[N],tk=,ss[N],sp=,os[N],op,q[N],ql,qr;

int n,m,D,idp,ans=,f1[N],f2[N];

void ae(int*e,int a,int b,int c){

    es[ep]=b;enx[ep]=e[a];ev[ep]=c;e[a]=ep++;

    es[ep]=a;enx[ep]=e[b];ev[ep]=c;e[b]=ep++;

}

int min(int a,int b){return a<b?a:b;}

void maxs(int&a,int b){if(a<b)a=b;}

void maxs(int&a,int&b,int c){

    if(a<=c)b=a,a=c;

    else if(b<c)b=c;

}

void tj(int w){

    dfn[w]=low[w]=++tk;

    for(int i=e0[w];i;i=enx[i]){

        int u=es[i];

        if(!u)continue;

        es[i^]=;

        if(!dfn[u]){

            ss[++sp]=u;

            tj(u);

            if(ss[sp]==u)--sp,ae(e1,w,u,);

        }else if((low[w]=min(low[w],dfn[u]))==dfn[u]){

            op=;

            while(sp&&dfn[ss[sp]]>dfn[u])os[++op]=ss[sp--];

            ae(e1,u,++idp,);

            for(int j=;j<=op;++j)ae(e1,idp,os[j],min(j,op+-j));

        }

    }

}

void dfs(int w,int pa){

    for(int i=e1[w];i;i=enx[i]){

        int u=es[i];

        if(u==pa)continue;

        dfs(u,w);

        maxs(f1[w],f2[w],f1[u]+ev[i]);

    }

    if(w<=n)maxs(ans,f1[w]+f2[w]);

    else{

        op=;

        for(int i=e1[w];i;i=enx[i]){

            int u=es[i];

            if(u!=pa)os[++op]=u;

        }

        os[++op]=pa;

        D=op>>;

        ql=,qr=;

        for(int i=;i<=D;++i)os[op+i]=os[i];

        op+=D;

        for(int i=;i<=op;++i){

            while(ql<=qr&&q[ql]+D<i)++ql;

            if(ql<=qr)maxs(ans,f1[os[q[ql]]]+f1[os[i]]-q[ql]+i);

            while(ql<=qr&&f1[os[q[qr]]]-q[qr]<=f1[os[i]]-i)--qr;

            q[++qr]=i;

        }

        ql=,qr=;

        for(int i=op;i;--i){

            while(ql<=qr&&q[ql]-D>i)++ql;

            if(ql<=qr)maxs(ans,f1[os[q[ql]]]+f1[os[i]]+q[ql]-i);

            while(ql<=qr&&f1[os[q[qr]]]+q[qr]<=f1[os[i]]+i)--qr;

            q[++qr]=i;

        }

    }

}

int main(){

    fread(buf,,sizeof(buf),stdin);

    idp=n=_();m=_();

    for(int i=,c,a,b;i<m;++i){

        c=_();

        a=_();

        for(int j=;j<c;++j){

            b=_();

            ae(e0,a,b,);

            a=b;

        }

    }

    tj();

    dfs(,);

    printf("%d",ans);

    return ;

}

2125 多次询问仙人掌上两点间最短路

任意两点a,b间距离分情况考虑，设c=lca(a,b)，若c是原有的点，则距离为树上a,b的距离dis(a,b)，否则设x,y分别为a,b到c的路径上与c最近的点，则距离为dis(a,x)+dis(b,y)+环上x,y间的距离

倍增或链剖求一下lca再用前缀和特判一下环上情况

#include<cstdio>

#include<algorithm>

char buf[],*ptr=buf-;

int _(){

    int x=,c=*++ptr;

    while(c<)c=*++ptr;

    while(c>)x=x*+c-,c=*++ptr;

    return x;

}

const int N=;

int n,m,q;

int es[N],enx[N],ev[N],e0[],e1[],ep=,ss[],sp=,idp,os[],op,d1[],d2[];

int dfn[],low[],tk=;

void ae(int*e,int a,int b,int c){

    es[ep]=b;enx[ep]=e[a];ev[ep]=c;e[a]=ep++;

    es[ep]=a;enx[ep]=e[b];ev[ep]=c;e[b]=ep++;

}

int min(int a,int b){return a<b?a:b;}

void f0(int w){

    dfn[w]=low[w]=++tk;

    for(int i=e0[w];i;i=enx[i]){

        int u=es[i];

        if(!u)continue;

        if(!dfn[u]){

            ss[++sp]=i;

            es[i^]=;

            f0(u);

            low[w]=min(low[w],low[u]);

            if(ss[sp]==i)--sp,ae(e1,w,u,ev[i]);

        }else if((low[w]=min(low[w],dfn[u]))==dfn[u]){

            ++idp;op=;

            ae(e1,idp,u,);

            op=;

            int s1=ev[i],s2=;

            while(sp&&dfn[es[ss[sp]]]>dfn[u]){

                int e=ss[sp--];

                os[op++]=e;

                s2+=ev[e];

            }

            for(int p=;p<op;++p){

                int e=os[p];

                ae(e1,idp,es[e],min(d1[es[e]]=s1,s2));

                d2[es[e]]=s1+s2;

                s1+=ev[e],s2-=ev[e];

            }

        }

    }

}

int fa[][],dep[],Dep[];

void f1(int w,int pa){

    fa[][w]=pa;

    for(int i=e1[w];i;i=enx[i]){

        int u=es[i];

        if(u==pa)continue;

        dep[u]=dep[w]+;

        Dep[u]=Dep[w]+ev[i];

        f1(u,w);

    }

}

int main(){

    fread(buf,,sizeof(buf),stdin);

    n=_();m=_();q=_();

    idp=n;

    for(int i=,a,b,c;i<=m;++i){

        a=_();b=_();c=_();

        ae(e0,a,b,c);

    }

    f0();

    f1(,);

    for(int i=;i<;++i)for(int j=;j<=idp;++j)fa[i][j]=fa[i-][fa[i-][j]];

    for(int i=,a,b,ans;i<q;++i){

        a=_();b=_();

        if(dep[a]<dep[b])std::swap(a,b);

        ans=Dep[a]+Dep[b];

        for(int d=,s=dep[a]-dep[b];d<;++d)if(s>>d&)a=fa[d][a];

        if(a==b)ans-=Dep[a]*;

        else{

            for(int d=;~d;--d)if(fa[d][a]!=fa[d][b])a=fa[d][a],b=fa[d][b];

            if(fa[][a]<=n)ans-=Dep[fa[][a]]*;

            else{

                ans-=Dep[a]+Dep[b];

                int s=d1[a]-d1[b];

                if(s<)s=-s;

                ans+=min(s,d2[a]-s);

            }

        }

        printf("%d\n",ans);

    }

    return ;

}

4728 带加点、加环操作维护仙人掌最长简单路径

对每条路径，路径上的点不会比两端更晚加入，所以可以离线处理

对新建的树点分治，分别考虑当前分治中心对应的子树（由于根改变，新边权要重新计算），若分治中心为环，则维护环上的前缀max/后缀max（由于环上两点间有两种路径，要分别维护），否则维护每个相邻点方向的最长路径

相关文章