首页 > 代码库 > bzoj 1023: [SHOI2008]cactus仙人掌图 2125: 最短路 4728: 挪威的森林 静态仙人掌上路径长度的维护系列
bzoj 1023: [SHOI2008]cactus仙人掌图 2125: 最短路 4728: 挪威的森林 静态仙人掌上路径长度的维护系列
%%% http://immortalco.blog.uoj.ac/blog/1955
一个通用的写法是建树，对每个环建一个新点，去掉环上的边，原先环上每个点到新点连边，边权为点到环根的最短/长路长度
1023 求仙人掌直径
树形dp，维护每个点向下的最长和次长路径长度，对原有的点直接更新答案，对新点可以把对应环上的点取出，倍长，破环成链，并用单调队列正反各扫一次
#include<cstdio>char buf[5000000],*ptr=buf-1;int _(){ int x=0,c=*++ptr; while(c<48)c=*++ptr; while(c>47)x=x*10+c-48,c=*++ptr; return x;}const int N=500007;int es[N],enx[N],ev[N],e0[N],e1[N],ep=2;int dfn[N],low[N],tk=0,ss[N],sp=0,os[N],op,q[N],ql,qr;int n,m,D,idp,ans=0,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^1]=0; if(!dfn[u]){ ss[++sp]=u; tj(u); if(ss[sp]==u)--sp,ae(e1,w,u,1); }else if((low[w]=min(low[w],dfn[u]))==dfn[u]){ op=0; while(sp&&dfn[ss[sp]]>dfn[u])os[++op]=ss[sp--]; ae(e1,u,++idp,0); for(int j=1;j<=op;++j)ae(e1,idp,os[j],min(j,op+1-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=0; for(int i=e1[w];i;i=enx[i]){ int u=es[i]; if(u!=pa)os[++op]=u; } os[++op]=pa; D=op>>1; ql=1,qr=0; for(int i=1;i<=D;++i)os[op+i]=os[i]; op+=D; for(int i=1;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=1,qr=0; 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,1,sizeof(buf),stdin); idp=n=_();m=_(); for(int i=0,c,a,b;i<m;++i){ c=_(); a=_(); for(int j=1;j<c;++j){ b=_(); ae(e0,a,b,1); a=b; } } tj(1); dfs(1,0); printf("%d",ans); return 0;}
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[1000000],*ptr=buf-1;int _(){ int x=0,c=*++ptr; while(c<48)c=*++ptr; while(c>47)x=x*10+c-48,c=*++ptr; return x;}const int N=100007;int n,m,q;int es[N],enx[N],ev[N],e0[20007],e1[20007],ep=2,ss[20007],sp=0,idp,os[20007],op,d1[20007],d2[20007];int dfn[20007],low[20007],tk=0;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^1]=0; 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=0; ae(e1,idp,u,0); op=0; int s1=ev[i],s2=0; while(sp&&dfn[es[ss[sp]]]>dfn[u]){ int e=ss[sp--]; os[op++]=e; s2+=ev[e]; } for(int p=0;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[16][20007],dep[20007],Dep[20007];void f1(int w,int pa){ fa[0][w]=pa; for(int i=e1[w];i;i=enx[i]){ int u=es[i]; if(u==pa)continue; dep[u]=dep[w]+1; Dep[u]=Dep[w]+ev[i]; f1(u,w); }}int main(){ fread(buf,1,sizeof(buf),stdin); n=_();m=_();q=_(); idp=n; for(int i=1,a,b,c;i<=m;++i){ a=_();b=_();c=_(); ae(e0,a,b,c); } f0(1); f1(1,0); for(int i=1;i<16;++i)for(int j=1;j<=idp;++j)fa[i][j]=fa[i-1][fa[i-1][j]]; for(int i=0,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=0,s=dep[a]-dep[b];d<16;++d)if(s>>d&1)a=fa[d][a]; if(a==b)ans-=Dep[a]*2; else{ for(int d=15;~d;--d)if(fa[d][a]!=fa[d][b])a=fa[d][a],b=fa[d][b]; if(fa[0][a]<=n)ans-=Dep[fa[0][a]]*2; else{ ans-=Dep[a]+Dep[b]; int s=d1[a]-d1[b]; if(s<0)s=-s; ans+=min(s,d2[a]-s); } } printf("%d\n",ans); } return 0;}
4728 带加点、加环操作维护仙人掌最长简单路径
对每条路径，路径上的点不会比两端更晚加入，所以可以离线处理
对新建的树点分治，分别考虑当前分治中心对应的子树（由于根改变，新边权要重新计算），若分治中心为环，则维护环上的前缀max/后缀max（由于环上两点间有两种路径，要分别维护），否则维护每个相邻点方向的最长路径
bzoj 1023: [SHOI2008]cactus仙人掌图 2125: 最短路 4728: 挪威的森林 静态仙人掌上路径长度的维护系列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。