仙人掌仙人掌定义一个无向连通图每条边要么不在环里要么只在一个环里。解决仙人掌问题的方法对于仙人掌我们可以使用dfs或圆方树(着重学习)来解决。圆方树众所周知树或森林有很好的性质并且容易通过很多常见数据结构维护。而一般图则没有那么好的性质所幸有时我们可以把一般图上的某些问题转化到树上考虑。而圆方树Block forest 或 Round-square tree就是一种将图变成树的方法。------------ 摘自0I Wiki前置知识1. Tarjan圆方树定义在圆方树中原图中的每个点对应一个圆点每一个点双连通分量对应一个方点。所以一张图的圆方树形态共有n c个点其中n是原图点数c是原图中点双连通分量的个数。而对于每一个点双连通分量这个点双连通分量中的每个点向它对应的方点连边。显然圆方树中每条边连接一个圆点和一个方点。下面的图显示了一张图和其圆方树形态。圆方树的构建我们发现圆方树的构建与点双连通分量有关所以我们选择使用Tarjan算法来实现。朴素的Tarjan算法使用了两个数组dfn[u]和low[u]和一个栈进行运算。dfn[u]表示第一次访问到u时它是第几个被访问的节点。low[u]表示u的DFS树中的子树中的某个点v能访问到的点的最小DFS序。Tarjan代码void tar(int u){ sta[top]u;dfn[u]cnt;low[u]cnt; for(int ihead[u];i!-1;iedge[i].nxt){ if(!dfn[edge[i].to]){ tar(edge[i].to); low[u]min(low[u],low[edge[i].to]); }else{ low[u]min(low[u],dfn[edge[i].to]); } } }搜索完之后我们可以知道在任意一个点双连通分量中深度最浅的点u,一定有dfn[u] low[u]。在找到点双连通分量时先让u和方点连边并将方点标号为n1开始的整数点双连通分量中除了u以外的其他的点都集中在栈顶端只需要不断弹栈直到弹出u的对应子节点为止即可。相信学过tarjan的都能理解吧当然我们可以同时处理被弹出的节点只要将其和新建的方点连边即可。代码如下void tar(int u){ dfn[u] low[u] cnt;sta[stop] u; mark[u] 1; for(int i g1.head[u];i;i g1.edge[i].nxt){ int v g1.edge[i].to; if(!dfn[v]){ tar(v); low[u] min(low[u],low[v]); if(low[v] dfn[u]){ g2.addedge(pcnt,u); g2.addedge(u,pcnt); int x 0; while(x ! v){ x sta[stop--]; g2.addedge(pcnt,x); g2.addedge(x,pcnt); mark[x] 0; } } }else if(mark[v]){ low[u] min(low[u],dfn[v]); } } return ; }这样就完成了对圆方树的构建。圆方树的性质圆方树有很优美的性质。无论如何换根圆方树形态不变因为你是把环连成菊花而不是别的什么圆方树的子树 原仙人掌的子仙人掌方点不会和方点相连。每一个方点对应一个点双联通分量方点的点度是点双联通分量的大小。还有其他的性质需要具体题目具体分析。例题1. 洛谷P5236【模板】静态仙人掌这题图中边上带有边权的仙人掌图所以我们需要对于图中每一个环都见建一个方点并连边。对于环外的点直接连边对于环中的点我们建立一个方点u,求出每个点v到u的父亲的最短路作为u - v的边权。我们发现对于每一个在环上的节点在原图中都只有两条路径到u的父亲。最后对于每一组询问我们需要分类讨论并用倍增或树剖解决。若两个点的lca是圆点直接求即可。若为方点则需求出该点的子节点中对应的两个点的祖先(A,B)答案即为两个点到他们祖先的距离 他们祖先之间的距离2. 洛谷P4320 道路相遇这题要求我们求图中两个点之间的路线必经的点的个数。显然对于在同一个点双连通分量的两个点没有必须经过的点。对于不在同一个点双连通分量的两个点如图。我们发现必经点的个数等于两个点之间圆点的个数即为路径长度/2 1。3. 洛谷P4630【APIO2018】铁人两项这题要求我们求有多少个三元组 s , c , f 满足存在一条简单路径从s出发经过c到达f。这里需要提到点双的一个性质对于一个点双中的两点它们之间简单路径的并集恰好完全等于这个点双。即同一个点双中的两不同点u,v之间一定存在一条简单路径经过给定的在同一个点双内的另一点w。下面是证明显然如果在简单路径出了点双就不可能再回到这个点双中否则会和点双的定义冲突。所以我们只需考虑证明一个点双连通图中任意三不同点u, v, c必存在一条从u到v的简单路径经过c。首先排除点数为2的情况它满足这个性质但是无法取出3个不同点。对于余下的情况我们建立网络流模型源点向c连容量为2的边u和v向汇点连容量为1的边。将原图中的双向边建成x向y一条容量为1的边和y向x一条容量为1的边。因为源点到c的边的容量为2那么如果这个网络最大流为2则证明一定有路径经过c。考虑最大流最小割定理显然最小割≤2接下来只要证最小割1。这等价于证明割掉任意一条容量为1的边是无法使源点和汇点不连通的。割掉u或v与汇点连接的点根据点双的第一种定义必然存在简单路径从c到另一个没割掉的点。割掉一个节点拆点形成的边这等价于删除一个点根据点双的定义余下的图仍然连通。割掉一条由原先的边建出的边这等价于删除一条边根据点双的定义显然存在路径。所以我们证明了最小割大于1即最大流等于2。证毕。所以两点在圆方树上的路径与路径上经过的方点相连的圆点的集合就等于原图中两点简单路径上的点集。回到题目对于一对s和f合法的c的数量等于s , f之间简单路径的并集的点数减2即去掉s , f本身。我们可以对圆方树上的点赋值将圆点赋为-1方点赋为点双的大小这样两圆点间圆方树上路径点权和恰好等于原图中简单路径并集大小减2。统计答案是我们记录每一个点的贡献即点权乘以经过它的路径条数利用树形dp即可。4. 洛谷P4244【SHOI2008】仙人掌图 II这题要求我们求出给定的仙人掌图的直径。我们可以从最简单的仙人掌开始考虑对于一颗树我们可以用树形DP求解最深次深1。那么将树换成仙人掌。首先我们建立圆方树。对于圆点处理方式与树相同最深次深1。对于方点转移为dp[i] dp[j] dis(i,j)dis(i,j)表示i点和j点之间的间距我们假定一个固定点i则我们需要求的就变为dp[j] dis(i,j)因为dis(i,j) min(j-i,n-ij)。而我们为了丢掉min( )函数方便使用单调队列我们破环为链再加倍将ij间距离超过半个环长的踢出队头因为每一次只考虑半个环长度的DP,显然这种方式时正确的最大值一定会被包含。5.CF487E Tourists这题要求我们求出图上a,b之间的路径中最低点值的最低可能值。上文介绍了一个性质对于一个点双中的两点它们之间简单路径的并集恰好完全等于这个点双。即同一个点双中的两不同点u,v之间一定存在一条简单路径经过给定的在同一个点双内的另一点w。所以如果a,b之间的路径会经过一个点双则一定可以取得该点双中的最小点权值。我们可以用tarjan遍历一遍再用树剖套线段树查询。但在菊花图上修改操作就会被卡成O(n ^ 2)的所以我们可以建立圆方树在方点上用mulitset维护整个点双的最小点权值,再用树剖套线段树完成查询。