仙人掌相关

基础

定义:每条边至多在一个简单环上的图。仙人掌是特殊的图,但没有树特殊,需要考虑环。

我们把一个环中 \(dfn\) 最小的点叫做环的根。

子仙人掌:以 \(r\) 为根的仙人掌上的点 \(p\) 的子仙人掌是从仙人掌中去掉 \(p\)\(r\) 的简单 路径上的所有边之后,\(p\) 所在的连通块 判断是否是仙人掌:\(dfs\) 树,边覆盖一下。

仙人掌求直径:\(DP\) ,不在环上的点直接最大值加次大值更新答案,对于每个环在上面 \(DP\), 单调队列跑一下。

仙人掌求最大独立集:记 \(f(i,j,k)\)\(i\) 的父节点状态为 \(j\)\(i\) 所在环顶状态为 \(k\) 时,\(i\) 为根的子树的最大独立集。这种定义方式在仙人掌中比较常见。

圆方树

把原本的点叫做圆点,对于每个环,多建一个代表的方点。原图中的非环边,直接连对应的圆圆边,环上的边不连了,而把环中的点向对应的方点都连一条边。就变成树了。

大概就是把环连成菊花,转化成树后就能干很多事情,比如 \(LCA\) ,虚树,点分治,仙人掌剖分,\(LCT\) 什么的。

建树就是刷点双的 \(Tarjan\) ,过程中连连边。

仙人掌最短路:建圆方树,就可以引入 \(LCA\) ,然后就很简单了。