仙人掌-圆方树学习笔记
仙人掌
仙人掌定义
一个无向连通图，每条边要么不在环里，要么只在一个环里。
解决仙人掌问题的方法
对于仙人掌，我们可以使用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 i=head[u];i!=-1;i=edge[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和方点连边，并将方点标号为n+1开始的整数，点双连通分量中除了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-i+j)。
而我们为了丢掉min( )函数方便使用单调队列，我们破环为链再加倍，将i，j间距离超过半个环长的踢出队头，因为每一次只考虑半个环长度的DP,显然这种方式时正确的，最大值一定会被包含。
5.CF487E Tourists
这题要求我们求出图上a,b之间的路径中最低点值的最低可能值。
上文介绍了一个性质：
对于一个点双中的两点，它们之间简单路径的并集，恰好完全等于这个点双。
即同一个点双中的两不同点u,v之间一定存在一条简单路径经过给定的在同一个点双内的另一点w。
所以，如果a,b之间的路径会经过一个点双，则一定可以取得该点双中的最小点权值。
我们可以用tarjan遍历一遍，再用树剖套线段树查询。
但在菊花图上，修改操作就会被卡成O(n ^ 2)的，所以我们可以建立圆方树，在方点上用mulitset维护整个点双的最小点权值,再用树剖套线段树完成查询。