圆方树

圆方树大约是处理仙人掌和一类点双问题的有力工具（咦，好像没啥差别）。

众所周知一张图的所有边双联通分量构成一个森林（连通图就是树）。

而点双联通分量则不是，因为一个割点会被包含在多个点双联通分量当中，我们其实可以看作，点双联通分量包含的是一系列边以及相关节点。

这东西很不好处理啊，我们大部分时候都不希望直接在图上做处理，我们更希望能够在结构相对简单的树上进行处理。

为了解决这个问题，圆方树应运而生。

构建

具体来说，对于一个点双联通分量，我们称里面所有的点为“圆点”。

然后我们对每个点双，都新建一个方点，断掉所有圆点之间的边，然后把这个点双里的圆点都连向方点。

最后会形成这样的一个结构（图源：陈俊锟，《平凡的圆方树和神奇的（动态）动态规划》）：

通常来说，方点作为“新建点”，保存的信息大多和它相连的圆点有关（因为我们其实是，选出了这个点双中的“代表节点”）。

比如 CF487E - Tourists 那道题里面就是保存圆点权值的最小值，但是这就会遇到一个问题，如果有修改操作，那么每次修改可能被卡到 \(O(nm)\)。

所以如果问题是带修的，我们可以钦定一个圆点为根，方点只维护儿子圆点的一些信息并，然后如果查询的 LCA 是方点，那么额外考虑方点的父亲圆点就行。

然后代码实现其实很简单，就是直接贺一下求点双的 Tarjan 板子。

然后我们考虑在加入点双的时候连边就行了。

不过唯一要注意的问题是弹栈，不要把割点本身弹出，它还要继续连边的。

Code

int tim = 0;
std::stack<int> s;
int dfn_o[si], low[si];
void Tarjan(int u) {
    s.push(u);
    low[u] = dfn_o[u] = ++tim;
    for(int i = head[u]; ~i; i = e[i].Next) {
        int v = e[i].ver;
        if(!dfn_o[v]) {
            Tarjan(v);
            low[u] = min(low[u], low[v]);
            if(low[v] >= dfn_o[u]) {
                int x;
                is_sq[++cnt] = true; // 其实这句话没有必要，因为方点编号都大于 n。
                do {
                    x = s.top(), s.pop();
                    G[x].push_back(cnt), G[cnt].push_back(x);
                } while(v != x);
                G[cnt].push_back(u), G[u].push_back(cnt);
            }
        }
        else low[u] = min(low[u], dfn_o[v]);
    }
}

习题看 2023 年七月和八月杂题选做就行了。

---

最后更新: July 14, 2023