口胡简单仙人掌图

· · 个人记录

而这里的仙人掌和我们学过的树是一样的，是指一种特殊的图

而无向图仙人掌的定义是：任意一条边至多只出现在一条简单回路的无向连通图称为仙人掌

而有向图仙人掌不仅满足上面的条件还要满足整个图是一个强连通分量

从图中可以直观理解，可以说仙人掌就是多个环拼接形成的图（图片来源于网络）

\text{部分简单的性质}

下面我们就从有向图中的仙人掌入手研究，但是我们可能会发现很难下手，回忆起第一次看到树的时候，我们就想到：

我们不妨用 dfs 树来研究仙人掌

研究横向边是研究 dfs 树的突破点之一

但你想了一下，发现仙人掌图竟然没有横向边？

是的，有了横向边就一定不是仙人掌，那怎么证明呢？

首先整个图是一个强连通分量，那么横向边指向的那个点一定可以回到根节点

  1. 顺着回路回去的时候和这个红点的祖先（除了蓝点）不相交

  1. 顺着回路回去的时候和这个红点的祖先（除了蓝点）相交

显然这两种情况都导致有边成为了多个回路的一部分

回忆起学 tarjan 的经验，看一看 dfn 与 low（所有后代 dfn 最小值） 的关系，可以发现有

这两个性质可以成为仙人掌的判定了吗？还不行，看图：

设红点为 v ，图片来自网络

可以看到 a 图中有两个儿子u，满足 low(u) < dfn(v)，那么红边属于了两个环了

可以看到 b 图中有一个儿子u，满足 low(u) < dfn(v)，还有一个回归边，那么红边也属于两个环

可以看到 c 图中有两条回归边，红边亦属于两个环内

所以还有性质3：若节点 v 有 A(v) 个儿子 u 满足 low(u) < dfn(v) ，而有 B(v) 个回归边，满足 A(v)+B(v)<2

判定完这三个性质就可以确定这个图是仙人掌（虽然不会证明）

\text{圆方树}

圆方树是无向图，圆方树怎么构建呢（先讲维护的操作是两点间最短路\log n 级别求）？

边权怎么敲定呢？

建好圆方树怎么搞呢？

求 u \to v 的最短路

我们先求出 x=LCA(u,v)

如果 x 是圆点，长度就是树上路径长度，证明显然，我们不会走额外的权值，给你个图：

如果 x 是方点，假设 U,V 分别是 u,v 的祖先，且是 x 的儿子

可以看出来 U,V 是方点的儿子，也就是在同一个环内，那么答案就是dis(U,V)+dis(u,U)+dis(v,V)

胡一下为什么这个算法是对的呢？

我们穿过任何一个环，其距离都是预处理好的，是最小的，再处理环内的答案即可，而就对 x 为圆点的，由于交点无环，所以不用处理环内答案

说一些细节：

\text{Code}