仙人掌和圆方树
panyf
·
·
个人记录
前置知识：无向图 Tarjan，基环树。
仙人掌
定义：
如果一张无向连通图（可以有重边）的每条边最多在一个简单回路内，则称它是一棵仙人掌 (Cactus)。
多棵仙人掌可以组成沙漠。
性质：n 个点的仙人掌边数不超过 2n-2。
证明：每个环都是一个点双连通分量。考虑 Tarjan 求点双连通分量的过程。设当前找到的环中 dfn 最小的点为 x，则 x 为割点，环中除了 x 以外的点都不可能在以后求出的环中出现。对于一个大小为 a 的环，有 a-1 个点不可能在以后的环中出现。最极端的情况是一个大小为 2 的环，此时有 1 个点不可能在以后的环中出现，边数可以取到上界 2n-2。
若不存在重边，则边数不超过 1.5(n-1)。
仙人掌找环
和基环树类似，仙人掌的题目通常需要环和非环边分别处理。仙人掌找环通常使用求割边的 Tarjan 算法。
算法流程：
设当前 dfs 到点 $x$，先对经过点 $x$ 的所有边遍历一遍，求出割边，割边即为非环边。之后对经过点 $x$ 的所有边再遍历一遍，处理环。若边 $(x,j)$ 满足 $dfn_j>dfn_x$ 且 $fa_j\neq x$，则 $(x,j)$ 在环上，且 $x$ 是环上 $dfn$ 最小的点，$j$ 是 $dfn$ 最大的点。对 $j$ 跳 $fa$ 即可求出整个环。先处理非环边再处理环，是因为部分题目（比如 [P4244 [SHOI2008]仙人掌图 II](https://www.luogu.com.cn/problem/P4244)），在处理环的时候需要用到非环边的信息。
注意如果有重边，dfs 时判断是否为树边要记录到达 $x$ 的边的编号，而不是 $x$ 在 dfs 树上的父亲（参考代码中记录的是父亲）。
参考代码：
```cpp
void tar(int x){
int i=he[x],j;
for(dfn[x]=low[x]=++id;i;i=ne[i])if(!dfn[j=to[i]]){
fa[j]=x,tar(j),low[x]=min(low[x],low[j]);
if(low[j]>dfn[x])/*处理非环边*/;
}else if(j!=fa[x])low[x]=min(low[x],dfn[j]);
for(i=he[x];i;i=ne[i])if(dfn[j=to[i]]>dfn[x]&&fa[j]!=x){//若存在重边此处 fa[j]!=x 和上一行 j!=fa[x] 应改为判断边的编号
for(;j!=x;j=fa[j])/*处理环*/;
}
}
```
对于不需要非环边和环分别处理的题目（比如 [P3180 [HAOI2016]地图](https://www.luogu.com.cn/problem/P3180)），也可以用求点双的 Tarjan 算法，每个环和非环边都是一个点双。
```cpp
void tar(int x){
dfn[x]=low[x]=++id,st[++tp]=x;
for(int i=he[x],j;i;i=ne[i])if(!dfn[j=to[i]]){
tar(j),low[x]=min(low[x],low[j]);
if(low[j]==dfn[x])for(;/*do something*/st[tp--]!=j;);
}else low[x]=min(low[x],dfn[j]);
}
```
## 仙人掌判定
Tarjan 的过程中，每找到一个环，除环中 $dfn$ 最小的点 $x$ 外，环中的点不可能在之后找到的环中出现。对点打标记判断即可。注意若判断不是仙人掌则立刻退出 dfs，否则时间复杂度会炸。
根据定义对环上的边打标记判断也行。
习题：
[P6335 [COCI2007-2008#1] STAZA](https://www.luogu.com.cn/problem/P6335)（dp） [题解](https://www.luogu.com.cn/blog/221955/solution-p6335)
[P4244 [SHOI2008]仙人掌图 II](https://www.luogu.com.cn/problem/P4244)（单调队列优化 dp）
[P3687 [ZJOI2017]仙人掌](https://www.luogu.com.cn/problem/P3687)（仙人掌判定+树形 dp）（此题不需要单独处理非环边，所以不需要 Tarjan）
[P3180 [HAOI2016]地图](https://www.luogu.com.cn/problem/P3180)（线段树合并）
[CF231E Cactus](https://www.luogu.com.cn/problem/CF231E)（Tarjan 将环缩点+lca，点仙人掌）
[CF901C Bipartite Segments](https://www.luogu.com.cn/problem/CF901C)（二分）
## 圆方树
圆方树可以将仙人掌的问题转化为树上问题求解。
很多树上算法都可以通过圆方树用于仙人掌，例如：仙人掌点分治、仙人掌链剖分、虚仙人掌、仙人掌哈希判同构等。
**定义**：
对于一棵仙人掌，将原图中的点作为圆点，对其中每个环新建一个方点，在方点和环上所有圆点间连边，保留原图中的非环边，即为圆方树。
**性质**：
1.圆方树是一棵树。设原图有 $n$ 个点，$m$ 个环，则原图有 $n-1+m$ 条边（树有 $n-1$ 条边，每加一个环就多一条边）。圆方树保留了所有非环边，对于每个大小为 $k$ 的环建了 $k$ 条圆方边，所以边数和原图相同。圆方树共有 $n$ 个圆点和 $m$ 个方点，总点数 $n+m$。又因为圆方树是连通图（显然环上的点通过圆方边仍然连通），所以圆方树是树。
根据以上性质容易发现圆方树的边数等于仙人掌边数，因此相关数组通常要开 $2$ 倍大小。
2.合法的圆方树（不存在方方边）和仙人掌一一对应。根据定义显然每个仙人掌对应一棵圆方树。将圆方树的方点去掉，将与其相连的圆点连成环，即可构造出一棵仙人掌，因此每棵圆方树对应一棵仙人掌。
**构造**：
利用仙人掌找环的算法即可。建边的时候通常可以只建一个方向。其实可以不写 Tarjan，先连圆方边，然后 $dfn_j>dfn_x$ 并且在圆方树上没有父亲的 $j$ 需要连圆圆边 $(x,j)$。
参考代码：
```cpp
//可以处理重边（视为长度为2的环）
const int N=1e5+3,M=2e5+3,O=4e5+3;
int he[N],to[O],ne[O],n,o,dfn[N],id,fa[N],f[M];//fa是原树的父亲，f是圆方树的父亲
basic_string<int>g[M];
void dfs(int x){
int i,j;
for(dfn[x]=++id,i=he[x];i;i=ne[i])if(!dfn[j=to[i]])fa[j]=x,dfs(j);
else if(dfn[j]>dfn[x])for(g[x]+=++o,f[o]=x;j!=x;j=fa[j])g[o]+=j,f[j]=o;//圆方边
}
int main(){
int x,i,j;
dfs(1);
for(x=1;x<=n;++x)for(i=he[x];i;i=ne[i])if(!f[j=to[i]]&&dfn[j]>dfn[x])g[x]+=j,f[j]=x;//圆圆边
}
```
Q:为什么对仙人掌建圆方树时通常不用广义圆方树的建法（即对非环边也建一个方点）？
A:大部分仙人掌的题目其实可以用广义圆方树，不过广义圆方树不满足圆方树的性质 2，在有重边且重边会造成影响的题目中不适用（因为加上或去掉重边之后对应的广义圆方树是相同的）。在部分特殊的题目中也不适用，例如：给定一棵仙人掌，多次询问点对 $u,v$ 间经过点不重复的路径数量。此题只能用仙人掌的圆方树，设 $x$ 为 $u,v$ 间方点个数，用 lca 求出，答案即为 $2^x$。
### 广义圆方树
对于一般无向图，对每个点双建一个方点，原图的点为圆点，方点和点双内所有圆点之间连边。
[P5236 【模板】静态仙人掌](https://www.luogu.com.cn/problem/P5236)
对于一个环，假设 dfs 序最小的点是 $x$，环对应的方点是 $y$，则 $y$ 向环上每个除 $x$ 以外的点 $i$ 连长度为 $dis(x,i)$ 的边，$x$ 向 $y$ 连长度为 $0$ 的边。
考虑询问 $(i,j)$ 的答案，求出 $l=lca(i,j)$，若 $l$ 为圆点，则记 $d_i$ 为圆方树上 $i$ 的带权深度，$d_i+d_j-2d_l$ 即为答案；否则求出 $u,v$ 表示路径 $(l,i),(l,j)$ 上的第二个点，$d_i+d_j-d_u-d_v+dis(u,v)$ 即为答案。
[CF487E Tourists](https://www.luogu.com.cn/problem/CF487E)
建出广义圆方树，然后就是单点修改链 $\min$，用全局平衡二叉树即可。
一些细节：对于方点，令其权值为儿子结点权值 $\min$，可以用可删堆维护。查询时若 lca 是方点，则和 lca 的父亲结点权值取 $\min$。
[#87. mx的仙人掌](https://uoj.ac/problem/87)
建出圆方树。对于每组询问的点建虚树。记 lca 为 $l$，分两种情况：
$l$ 为圆点：对于 $l$ 的每个儿子 $i$，求出 $a_i$ 表示 $i$ 子树内的询问点到 $i$ 的距离的最大值，对答案的贡献即为 $\max_{i,j} (a_i+len(l,i))+(a_j+len(l,j))$。
$l$ 为方点：贡献为 $\max_{i,j} a_i+a_j+dis(i,j)$，可以用单调队列优化做到线性。
参考资料：[圆方树——处理仙人掌的利器 immortalCO](https://immortalco.blog.uoj.ac/blog/1955)