仙人掌的相关概念

仙人掌： 对于任意一条边至多只出现在一条简单回路的无向连通图称为仙人掌。

仙人掌相关题目的核心思路：

由于仙人掌中每条边最多只会出现在一个环里，因此如果我们将所有环进行缩点，则整个仙人掌必然会形成一棵树。

此时对于原问题我们就可以转化成一个树上问题，然后我们就可以用求树上问题的算法来做，而树上问题相关的算法则非常多：$LCA$、树形 $dp$、树链剖分、点分治等等，根据题目的要求这些树上算法都可能会用到。

可以发现仙人掌本身的思路并不复杂，问题在于仙人掌往往会搭配多个知识点一起考察，导致难度大增。

如何将仙人掌转化成圆方树：

圆方树是一棵有向树。

首先从仙人掌中任意找一个点作为根节点。当我们的根节点确定之后，我们在每一个环上都可以找到一个唯一的点，使得这个点到根节点的距离最近，我们把这个点称为它所在环的头。而对于根节点所在的环，根节点就是所在环的头。此时每个环中都有两类点，头节点和其他的点。

然后我们将仙人掌中的每一个环都变形。我们规定仙人掌中原有的所有点都是圆点。对于任意一个环，我们先对于这个环建立一个方点，然后从这个环的头节点向方点连一条有向边，从方点向这个环的其他点连一条有向边。然后我们令从头节点向方点连的边的权值是 $0$，而从方点连向其余点的边的权值定义为这个点到头节点的最短距离。剩下所有环外的边保持不变。这样我们就将所有环拆开了，拆开的同时还能保证原图中头节点和每个点的最短距离等于新图中头节点和每个点的最短距离，并且这样拆开之后整个仙人掌就会变成一棵树（原图中圆点与圆点之间确定为从根节点向下的方向），这样一棵有向树就称为圆方树。

将仙人掌变成圆方树的具体思路已经比较明确，接下来我们还需要考虑如何去实现出来，这里需要用到求边双连通分量的 $tarjan$ 算法，可以在线性的时间复杂度内求出边双连通分量，我们可以用 $tarjan$ 算法求出仙人掌中所有的环，但是当一个点同时延伸出两个环时，这两个环会被看作一整个双连通分量，因此我们需要在 $tarjan$ 算法的基础上稍作改动，每遍历一个点时，如果这个点存在一个环，则会有一条出边和一条入边，如果这个点存在多个环，则会有多条出边和多条入边，我们判断一下这个点出去的所有儿子，如果某个儿子不是这个点的子节点，说明存在一个环，而这个儿子就是通过环在前面就被访问过了，此时就找出了一个环，按照这个方法可以找出所有的环。找出所有环之后，对于每个环，而我们在 $tarjan$ 算法中第一个遍历到的点就是头节点，同时我们还能求出环上所有的点，我们从方点向头节点以外的点连一条边，再从头节点向方点连一条边，这里还要求一下头节点到每个点的权值，这里需要在头节点到该点的两条路径中取一个权值最小值，这里可以记录环中从头节点开始顺时针方向的前缀和，头节点规定为环的总长度，我们在求环的过程中预处理出每个点的前缀和，这样环中任意一段路径和就能通过 $O(1)$ 的时间计算出来，然后就能给每条边赋上权值，这样圆方树就建完了。

接下来原题的问题就变成了一个树上的问题，只需要用求树上问题的算法去进一步求解。但是对于某些题，仙人掌中的问题可能无法直接映射成圆方树上的问题，此时我们还需要分类讨论，并搭配一些技巧去解决这方面的问题。