圆方树 就是一种将图变成树的方法。可以把图的问题转化为树上问题。
仙人掌
定义
仙人掌（学名：Opuntia stricta (Haw.) Haw. var. dillenii (Ker-Gawl.) Benson ）石竹沙漠植物，是仙人掌科缩刺仙人掌的变种。
它的图片是这样的：
才怪。
仙人掌指的是每条边在不超过一个简单环中的无向图。
下面有一些仙人掌。
圆方树
定义
圆方树是处理仙人掌上问题的一种工具，它的思想很简单，就是把图中每一个简单环变成菊花图的形状。用圆点表示原图上的点，方点表示新增的辅助点。
下面有一些示意图。
应用
圆方树可以用来处理一些简单的问题。
例题可以看我的博客。
广义圆方树
定义
广义圆方树是处理一般图上问题的一种工具，它的思想很简单，就是把图中每一个点双连通分量变成菊花图。
要介绍广义圆方树，首先要介绍点双连通分量。
一个点双连通图的一个定义是：图中任意两不同点之间都有至少两条点不重复的路径。
点不重复既指路径上点不重复（简单路径），也指两条路径的交集为空（当然，路径必然都经过出发点和到达点，这不在考虑范围内）。
可以发现对于只有一个点的图比较难定义它是不是一个点双，这里先不考虑节点数为 $1$ 的图。
一个近乎等价的定义是：不存在割点的图。
这个定义只在图中只有两个点，一条连接它们的边时失效。它没有割点，但是并不能找到两条不相交的路径，因为只有一条路径。
（也可以理解为那一条路径可以算两次，的确没有交，因为不经过其他点）
虽然原始的定义的确是前者，但是为了方便，我们规定点双图的定义采用后者。
而一个图的点双连通分量则是一个极大点双连通子图。
与强连通分量等不同，一个点可能属于多个点双，但是一条边属于恰好一个点双（如果定义采用前者则有可能不属于任何点双）。
在圆方树中，原来的每个点对应一个圆点，每一个点双对应一个方点。
所以共有 $n+c$ 个点，其中 $n$ 是原图点数，$c$ 是原图点双连通分量的个数。
而对于每一个点双连通分量，它对应的方点向这个点双连通分量中的每个点连边。
每个点双形成一个“菊花图”，多个“菊花图”通过原图中的割点连接在一起（因为点双的分隔点是割点）。
显然，圆方树中每条边连接一个圆点和一个方点。
下面有一张图，来自 WC 的 PPT，显示了一张图对应的点双和广义圆方树形态。
应用
广义圆方树的应用比较广泛，下面是相应例题。
近期评论