仙人掌&圆方树总结

## 仙人掌&圆方树总结 学了好长时间了，也该写一个总结了 ### 仙人掌  #### 定义： 每条边最多包含在一个环中的连通图  #### 性质及操作： 其实就是无向的基环树的一般形式，所以仙人掌的操作**可以直接套到基环树上使用** 由于每条边最多在一个环中 所以可以分成树上和环上（拆成一条链（本质还是树上））分别$DP$ #### 实现 $Tarjan$算法可以很好的实现这一操作 我们发现 $Tarjan$算法本质上还是一棵搜索树 在树边上 即$low[y]>dfn[x]$时直接$DP$ 遇到环 即$dfn[x]==low[y]\&\&fa[y]!=x$时进入环然后$DP$ 最后用环上的答案更新根节点$x$ **环上其他点的答案不更新** $dfn[x]==low[y]\&\&fa[y]!=x$就是这种情况  判环的代码 ```cpp void tarjan(int x,int ff)//仙人掌的tarjan记录一下父亲 { dfn[x]=low[x]=++clk; fa[x]=ff; dep[x]=dep[ff]+1; for(int i=head[x];i;i=e[i].nxt) { int y=e[i].to; if(!dfn[y]){ tarjan(y,x); low[x]=min(low[x],low[y]); } else if(y!=ff)low[x]=min(low[x],dfn[y]); if(dfn[x]<low[y]) //两个点不看做点双 只有在low[y]==dfn[x]才代表一个环 { ans=max(ans,f[x]+f[y]+1); f[x]=max(f[x],f[y]+1); } } for(int i=head[x];i;i=e[i].nxt) { int y=e[i].to; if(low[y]==dfn[x]&&fa[y]!=x)//x是环的起始点 y是环的终点 只有这是才进入 dp(x,y); } } ``` [P4244 [SHOI2008]仙人掌图 II](https://www.luogu.org/problemnew/show/P4244) 求仙人掌的直径 直接按树的直径做 环中断环为链用单调队列做即可 环中树的直径方程可以写为 $max(f[i]+f[j]+j-i)$， 固定$i$之后就是求 $max(f[j]+j),(j\in [i-\frac{n}{2},i-1])$ 上单调队列就行了 ```cpp #include<bits/stdc++.h> using namespace std; const int maxn=55555; struct edge{ int to,nxt,w; }e[maxn<<3]; int dfn[maxn],dep[maxn],clk,n,m,low[maxn],fa[maxn],f[maxn],head[maxn],tot; inline void add(int x,int y,int z) { e[++tot].to=y; e[tot].w=z; e[tot].nxt=head[x]; head[x]=tot; } int ans=1; int q[maxn<<1],a[maxn<<1]; void dp(int x,int y)//求好的dp值只更新根节点 { int top=0; for(int i=y;i!=x;i=fa[i])a[++top]=i;//记录环的点 a[++top]=x; reverse(a+1,a+1+top); for(int i=top+1;i<=top+top;i++)a[i]=a[i-top];//断环为链 复制一倍 int h=1,t=0; for(int i=1;i<=top*2;i++) { while(h<=t&&i-q[h]>top/2)h++; if(h<=t)ans=max(ans,f[a[i]]+f[a[q[h]]]+i-q[h]); while(h<=t&&f[a[i]]-i>f[a[q[t]]]-q[t])t--; q[++t]=i; } for(int i=y;i!=x;i=fa[i])//更新环顶端的答案 f[x]=max(f[x],f[i]+min(dep[i]-dep[x],dep[y]-dep[i]+1)); } void tarjan(int x,int ff)//仙人掌的tarjan记录一下父亲 { dfn[x]=low[x]=++clk; fa[x]=ff; dep[x]=dep[ff]+1; for(int i=head[x];i;i=e[i].nxt) { int y=e[i].to; if(!dfn[y]){ tarjan(y,x); low[x]=min(low[x],low[y]); } else if(y!=ff)low[x]=min(low[x],dfn[y]); if(dfn[x]<low[y]) //两个点不看做点双 只有在low[y]==dfn[x]才代表一个环 { ans=max(ans,f[x]+f[y]+1); f[x]=max(f[x],f[y]+1); } } for(int i=head[x];i;i=e[i].nxt) { int y=e[i].to; if(low[y]==dfn[x]&&fa[y]!=x)//x是环的起始点 y是环的终点 只有这是才进入 dp(x,y); } } int main() { // freopen("20.in","r",stdin); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int k,a; scanf("%d%d",&k,&a); for(int j=1;j<k;j++) { int b; scanf("%d",&b); add(a,b,1);add(b,a,1); a=b; } } tarjan(1,0); printf("%d\n",ans); } ``` ~~过渡句~~那么这和圆方树有什么关系呢? 其实 圆方树可以处理大多数仙人掌问题 只不过有时候没必要建出来罢了 ### 圆方树 就是把一个图上的所有的树点作为原点 把环拆掉弄成一个方点所形成的树 ~~偷过来的几张图~~ 原图  圆方树  #### 狭义圆方树 就是在仙人掌上建的圆方树 有一个性质 圆方树的子树等于子仙人掌 同仙人掌$DP$的判环方法一样 直接进入环然后新建一个方点和环上所有点连边就行了 要把那些点的信息记录到方点上 把圆点和方点附加合适的权值 原图中的树边直接连 为了方便一般开两个结构体$G\ T$存边 建树 从$x$进入 ```cpp void tarjan(int x,int f)//仙人掌的tarjan记录一下父亲 { dfn[x]=low[x]=++clk;dep[x]=dep[f]+1;fa[x]=f; for(int i=G.head[x];i;i=G.e[i].nxt) { int y=G.e[i].to; if(y==f)continue; if(!dfn[y]) { dis[y]=dis[x]+G.e[i].w; tarjan(y,x); low[x]=min(low[x],low[y]); } else low[x]=min(low[x],dfn[y]); if(dfn[x]<low[y])T.add(x,y,G.e[i].w);//两个点之间不看作点双 所以要这样特判一下 是两个点组成的点双 其他情况直接特判build 圆点之间的边连原图的边权 } for(int i=G.head[x];i;i=G.e[i].nxt) { int y=G.e[i].to; if(y==f)continue; if(fa[y]!=x&&dfn[x]==low[y])build(x,y,G.e[i].w);//只有到u是环中第一个点 v是环中最后一个点时才会build 从v一直跳father时会少算u到v的这条边 所以要加上 } } void build(int x,int y,int d) { int top=dep[y]-dep[x]+1,sum=d,Dis=0; for(int i=y;i!=x;i=fa[i])//S中存环 S[top--]=i,sum+=dis[i]-dis[fa[i]];//整个环的距离 tot++; S[1]=x;//S[top]为y top=dep[y]-dep[x]+1;//环上的点数 RST.cir[tot]=sum;//方点存整个环的边权 for(int i=1;i<=top;i++) { int D=min(Dis,sum-Dis);//从y另一边走到u的距离和从y这边走的距离取min T.add(tot,S[i],D); RST.zn[S[i]]=(D==Dis);//从y另一边边走更近 zn记录每个点到达深度最小的点是否经过返祖边(即u-y) Dis+=dis[S[i+1]]-dis[S[i]];//从另一边走的距离累加上去 } } ``` [P5236 【模板】静态仙人掌](https://www.luogu.org/problemnew/show/P5236) 求仙人掌最短路 直接$DP$显然不行了 要建出圆方树 用树剖+线段树维护两点间的距离 ```cpp #include<bits/stdc++.h> using namespace std; const int maxn=20000+100; struct edge{ int to,nxt,w; }; struct graph{ edge e[111111]; int head[maxn],tot; inline void add(int x,int y,int z) { e[++tot].to=y,e[tot].w=z,e[tot].nxt=head[x];head[x]=tot; e[++tot].to=x,e[tot].w=z,e[tot].nxt=head[y];head[y]=tot; } }T,G;//G仙人掌 T圆方树 int n; struct RST{ int fa[maxn],siz[maxn],son[maxn],top[maxn],dep[maxn],dis[maxn]; int dfn[maxn],nfd[maxn],clk,cir[maxn];//nfd 相反的dfn bool zn[maxn];//是否经过返祖边 void dfs1(int x) { siz[x]=1; for(int i=T.head[x];i;i=T.e[i].nxt) { int y=T.e[i].to; if(y==fa[x])continue; fa[y]=x;dep[y]=dep[x]+1;dis[y]=dis[x]+T.e[i].w; dfs1(y); siz[x]+=siz[y]; if(siz[y]>siz[son[x]])son[x]=y; } } void dfs2(int x,int topf) { dfn[x]=++clk;nfd[clk]=x;top[x]=topf; if(son[x])dfs2(son[x],topf); for(int i=T.head[x];i;i=T.e[i].nxt) { int y=T.e[i].to; if(y==son[x]||y==fa[x])continue; dfs2(y,y); } } int LCA(int x,int y) { while(top[x]!=top[y]){ if(dep[top[x]]>dep[top[y]])x=fa[top[x]]; else y=fa[top[y]]; } return dep[x]<dep[y]?x:y; } int find(int x,int lca) { int ret; while(top[x]!=top[lca]) ret=top[x],x=fa[top[x]]; return x==lca?ret:nfd[dfn[lca]+1];//ret u跳过来的轻儿子 否则就是重儿子 } int query(int x,int y) { int lca=LCA(x,y);//这里的dis是圆方树上的dis if(lca<=n)return dis[x]+dis[y]-2*dis[lca];//<=n的点是圆点 int fax=find(x,lca),fay=find(y,lca); int d1=dis[fax]-dis[lca],d2=dis[fay]-dis[lca];//此后为了算两个祖先之间的最短路 if(!zn[fax])d1=cir[lca]-d1;//dis只是为了调整到走的方向一致 改到同一侧 if(!zn[fay])d2=cir[lca]-d2; return dis[x]-dis[fax]+dis[y]-dis[fay]+min(abs(d1-d2),cir[lca]-abs(d1-d2)); } }RST; //G是仙人掌 T是圆方树 int dfn[maxn],low[maxn],clk,tp[maxn],dep[maxn],fa[maxn]; long long dis[maxn];//这里的fa和dis都是tarjan搜索树上的 以便计算环的长度 int S[maxn],tot,m,Q; void build(int x,int y,int d) { int top=dep[y]-dep[x]+1,sum=d,Dis=0; for(int i=y;i!=x;i=fa[i])//S中存环 S[top--]=i,sum+=dis[i]-dis[fa[i]];//整个环的距离 tot++; S[1]=x;//S[top]为y top=dep[y]-dep[x]+1;//环上的点数 RST.cir[tot]=sum;//方点存整个环的边权 for(int i=1;i<=top;i++) { int D=min(Dis,sum-Dis);//从y另一边走到u的距离和从y这边走的距离取min T.add(tot,S[i],D); RST.zn[S[i]]=(D==Dis);//从y另一边边走更近 zn记录每个点到达深度最小的点是否经过返祖边(即u-y) Dis+=dis[S[i+1]]-dis[S[i]];//从另一边走的距离累加上去 } } void tarjan(int x,int f)//仙人掌的tarjan记录一下父亲 { dfn[x]=low[x]=++clk;dep[x]=dep[f]+1;fa[x]=f; for(int i=G.head[x];i;i=G.e[i].nxt) { int y=G.e[i].to; if(y==f)continue; if(!dfn[y]) { dis[y]=dis[x]+G.e[i].w; tarjan(y,x); low[x]=min(low[x],low[y]); } else low[x]=min(low[x],dfn[y]); if(dfn[x]<low[y])T.add(x,y,G.e[i].w);//两个点之间不看作点双 所以要这样特判一下 是两个点组成的点双 其他情况直接特判build 圆点之间的边连原图的边权 } for(int i=G.head[x];i;i=G.e[i].nxt) { int y=G.e[i].to; if(y==f)continue; if(fa[y]!=x&&dfn[x]==low[y])build(x,y,G.e[i].w);//只有到u是环中第一个点 v是环中最后一个点时才会build 从v一直跳father时会少算u到v的这条边 所以要加上 } } int main() { scanf("%d%d%d",&n,&m,&Q); tot=n; for(int i=1;i<=m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); G.add(x,y,z); } tarjan(1,0); RST.dfs1(1); RST.dfs2(1,1); while(Q--){ int x,y; scanf("%d%d",&x,&y); printf("%d\n",RST.query(x,y)); } } ``` #### 广义圆方树 建在无向图上的圆方树 就是这样  由于是无向图 不存在树边 所以把两个点也视为点双 建立一个方点 所以 广义圆方树**圆方点交替** 构建方法也比较简单 直接判断点双即$low[y]>=dfn[x]$即可 用$T$建立圆方树 ```cpp void Tarjan(int x) { dfn[x]=low[x]=++tim;stac[++top]=x; for(int i=G.head[x];i;i=G.e[i].nxt) { int y=G.e[i].to; if(!dfn[y]) { Tarjan(y);low[x]=min(low[x],low[y]); if(low[y]>=dfn[x]) { T.add(++tot,x); int u; do{ u=stac[top--]; T.add(tot,u); }while(y!=u); } } else low[x]=min(low[x],dfn[y]); } } ``` 由于是点双 所以圆点就是图中的割点 两点之间的圆点就是必经点 考虑做法时也是先考虑树上的然后再考虑把圆点的信息转移到方点上 [CF487E Tourists](https://www.luogu.org/problemnew/show/CF487E) 每次修改一个点 求原图中两点间路径上的最小值 建立圆方树 用方点开一个$set$维护相连的圆点上的值 树剖+线段树维护一下即可 注意方点要只维护儿子圆点的信息 如果维护一圈的话 一个菊花图 根是圆点 每次需要修改$n$个$set$ $T$的飞起 这样就行了 ```cpp #include<bits/stdc++.h> #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 using namespace std; const int maxn=500000; struct edge{ int to,nxt; }; struct graph{ int head[maxn],tot; edge e[maxn<<1]; void add(int x,int y) { e[++tot].to=y;e[tot].nxt=head[x];head[x]=tot; e[++tot].to=x;e[tot].nxt=head[y];head[y]=tot; } }T,G; multiset<int> minn[maxn]; int n,m,q,tot,w[maxn];//tot 从n开始编号 大于n的是方点 struct Graph { int dfn[maxn],low[maxn],stac[maxn],tim,top; void Tarjan(int x) { dfn[x]=low[x]=++tim;stac[++top]=x; for(int i=G.head[x];i;i=G.e[i].nxt) { int y=G.e[i].to; if(!dfn[y]) { Tarjan(y);low[x]=min(low[x],low[y]); if(low[y]>=dfn[x]) { T.add(++tot,x); int u; do{ u=stac[top--]; T.add(tot,u); }while(y!=u); } } else low[x]=min(low[x],dfn[y]); } } }Gr; int minv[maxn<<2]; void update(int pos,int val,int l,int r,int rt) { if(l==r){ minv[rt]=val;return ; } int m=l+r>>1; if(pos<=m)update(pos,val,ls); else update(pos,val,rs); minv[rt]=min(minv[rt<<1],minv[rt<<1|1]); } int query(int L,int R,int l,int r,int rt)//Çø¼ämin { if(L<=l&&r<=R)return minv[rt]; int m=l+r>>1,ret=INT_MAX; if(L<=m)ret=min(ret,query(L,R,ls)); if(R>m)ret=min(ret,query(L,R,rs)); return ret; } int fa[maxn],DFN[maxn],siz[maxn],top[maxn],dep[maxn],CLK,son[maxn]; void dfs1(int x) { siz[x]=1;dep[x]=dep[fa[x]]+1; if(x<=n&&fa[x])minn[fa[x]].insert(w[x]); for(int i=T.head[x];i;i=T.e[i].nxt) { int y=T.e[i].to; if(y==fa[x])continue; fa[y]=x; dfs1(y); siz[x]+=siz[y]; if(siz[y]>siz[son[x]])son[x]=y; } } void dfs2(int x,int topf) { top[x]=topf;DFN[x]=++CLK; if(son[x])dfs2(son[x],topf); for(int i=T.head[x];i;i=T.e[i].nxt) { int y=T.e[i].to; if(y==son[x]||y==fa[x])continue; dfs2(y,y); } } int ask(int x,int y) { int ret=INT_MAX; while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]])swap(x,y); ret=min(ret,query(DFN[top[x]],DFN[x],1,tot,1)); x=fa[top[x]]; } if(dep[x]>dep[y])swap(x,y); ret=min(ret,query(DFN[x],DFN[y],1,tot,1)); return x<=n?ret:min(ret,w[fa[x]]);//方点只包括父亲，需要特判一下两个点的祖先圆点 } void modify(int x,int val) { if(fa[x])//强行让方点的权值不包括他的儿子 只记录父亲 因为园方点交替 x是圆点 fa一定是方点 { minn[fa[x]].erase(minn[fa[x]].find(w[x])); minn[fa[x]].insert(val); update(DFN[fa[x]],*minn[fa[x]].begin(),1,tot,1); } w[x]=val;update(DFN[x],val,1,tot,1); } int main() { scanf("%d%d%d",&n,&m,&q);tot=n;w[0]=INT_MAX; for(int i=1;i<=n;i++)scanf("%d",&w[i]); for(int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); G.add(x,y); } Gr.Tarjan(1); dfs1(1);dfs2(1,1); for(int i=1;i<=n;i++)update(DFN[i],w[i],1,tot,1); for(int i=n+1;i<=tot;i++)update(DFN[i],*minn[i].begin(),1,tot,1);//修改方点的值，只记录儿子中最小的，方便经过方点时直接取最小权值 char ch[2]; while(q--) { scanf("%s",ch); int a,b; scanf("%d%d",&a,&b); if(ch[0]=='C')modify(a,b); else printf("%d\n",ask(a,b)); } } ``` [P4630 铁人两项](https://www.luogu.org/problem/P4630) 从树上推到图上 ```cpp #include<bits/stdc++.h> using namespace std; const int maxn=201000; struct edge{ int to,nxt; }; struct graph{ edge e[maxn<<1]; int head[maxn],tot; void add(int x,int y) { e[++tot].to=y;e[tot].nxt=head[x];head[x]=tot; e[++tot].to=x;e[tot].nxt=head[y];head[y]=tot; } }G,T; int n,m,tot,w[maxn],cnt; struct Tarjan{ int dfn[maxn],low[maxn],clk,stac[maxn],top; void tarjan(int x) { dfn[x]=low[x]=++clk;stac[++top]=x;cnt++; for(int i=G.head[x];i;i=G.e[i].nxt) { int y=G.e[i].to; if(!dfn[y]) { tarjan(y); low[x]=min(low[x],low[y]); if(dfn[x]<=low[y]) { T.add(++tot,x); w[tot]++; int u; do{ u=stac[top--]; T.add(tot,u); w[tot]++; }while(y!=u); } } else low[x]=min(low[x],dfn[y]); } } }Tar; int siz[maxn]; long long ans; void dfs(int x,int f) { siz[x]=(x<=n);//方点是虚拟节点 圆点才是原图中的点 所以统计时方点不计size for(int i=T.head[x];i;i=T.e[i].nxt) { int y=T.e[i].to; if(y==f)continue; dfs(y,x); ans+=2ll*siz[y]*siz[x]*w[x];//枚举中间点 siz[x]+=siz[y]; } ans+=2ll*siz[x]*(cnt-siz[x])*w[x]; } int main() { scanf("%d%d",&n,&m);tot=n; int x,y; for(int i=1;i<=n;i++)w[i]=-1; for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); G.add(x,y); } for(int i=1;i<=n;i++) if(!Tar.dfn[i]) { cnt=0;Tar.top=0; Tar.tarjan(i); dfs(i,0); } cout<<ans; } ``` ## 没了