圆方树学习笔记

· · 个人记录

由于图比树要复杂，所以我们解决图论题时有时会把图变成树。

圆方树就是一种将图变为树的方法。

狭义圆方树一般指仙人掌所建的圆方树。广义圆方树指无向连通图的所建成的圆方树。

仙人掌是什么？

仙人掌是所有的边最多在一个简单环上的特殊的无向连通图。如图：

前置知识：tarjan求点双联通分量，基础图论，树论。

P.S. 求点双模板代码。

1.1 狭义圆方树的概念

将仙人掌上的，每个环都建一个方点。对于剩下的边我们再建一个方点夹在边的两点之间。 最后，将每个点向所在的环对应的方点连边。如此，则圆方树方点圆点交错矣。

如图：

绿色为新建的圆方树边，红色的方形为方点，黑色的圆形为圆点。从图上就可以看出来，建出来的点数是 O(n) 的。

多形象啊，圆方树。

1.2 广义圆方树的概念

广义圆方树即把无向连通图的点双看成仙人掌上的环，将点向点双所对应的方点连边即可。

1.3 建圆方树

在学建圆方树前，您必须学会点双。

不会点双？巧了我也不会您可以去 OI Wiki 的圆方树专题看看，有 tarjan 求点双的介绍。

其实只需要将求点双的代码稍作修改即可，其实就是将所有点双中的点连向一个新建的方点。

我们的编号小于等于 N 的节点为圆点，大于 N 的节点为方点。

如下：

auto addedge = [&](i64 x, i64 y) { // 圆方树上建边
    rst[x].push_back(y);
    rst[y].push_back(x);
};

i64 cnt = 0, tot = N; // tot记录的是方点的最大编号
auto tarjan = [&](auto self, i64 x, i64 fa) -> void {
    low[x] = dfn[x] = ++cnt;
    stk.push(x);
    for (auto p : G[x]) {
        i64 v = p.first, w = p.second;
        if (dfn[v]) {
            if (v != fa) {
                low[x] = std::min(low[x], dfn[v]);
            }
            continue;
        }
        self(self, v, x);
        low[x] = std::min(low[x], low[v]);
        if (low[v] >= dfn[x]) { // 为什么不是等于呢？因为我们要将剩下的边处理二元环，中间加入一个节点。
            i64 kk = 0; tot++;
            while (kk != v) {
                addedge(stk.top(), tot); // 记录点双改为建边
                kk = stk.top(); stk.pop();
            }
            addedge(x, tot); // 最后一定要将当前节点加入，但是不要弹栈。
        }
    }
};

2.1 例题1 P4630 [APIO2018] 铁人两项

题目大意：问你一张图上按顺序选择三个点 x, y, z，使得可以用按顺序走，能走出一条简单路径，开头是 x，中间是y，后面是 z。求方案数。

我们发现，当我们建出广义圆方树后，情况是这样的：

如图，我们在图上原本就不能连成一条简单路径的三个点，在圆方树上一定也连不出来。

比如图上的 x = 4, y = 8, z = 2 在圆方树和原图上都走不出来。

同时我们发现，选取了开头和结尾，圆方树两点之间的所有点代表的点双分量的所有点都可以走出简单路径。

所以我们考虑到中间的节点不好处理，可以做一个变换，将中间节点的可以取的点的个数作为圆方树上点的权值，最后查询的就是圆方树上所有以圆点为端点的简单路径的权值之和。

怎么构造点权呢？容易想到，方点上的点权应该取她所代表的点双分量的点数。而会有点会存在于多个点双分量中，所以所有圆点的点双分量设为 -1，从而可以减去自己重复计算入路径。

我们考虑每个点会被多少条边经过，然后乘上自己点的权值，再乘以2（可以反过来走，把终点变为起点）就是答案了（其实就是计算贡献）。然后就是一个简单的树形 dp 了。详细见代码。

代码

2.2 例题2 UVA1464 Traffic Real Time Query System

题目大意：给你一张无向连通图和 q 次询问，每次询问给出两条原图上的边，问你从这条边到另一条边中间不可避免要经过多少点。

我们先只考虑两点之间的情况。

我们一眼就可以看出，必须要经过的点就是那两点之间的割点。

考虑建出圆方树，我们会发现他就是在问两点中间（不含两点）有多少个圆点。

如图：

标绿色三角形的是询问的两个点。绿色路径是两点在圆方树上的简单路径，蓝色是我们可能会选择的图上路径。

她们必须经过4号点和6号点。

这样就简单多了，就是一个普通的树上距离问题了。最后要求的就是距离除以2减去1。（圆方树上方圆相间）

还有，就是题目问的是两条边啊！那就把第一条边的两个端点和第二条边的两个端点两两组合，然后取答案的最大值。

我的毒瘤码风在 UVA C++11 过不了编，被迫改码风

代码

2.3 例题3 P5236 【模板】静态仙人掌

本来这不会是一道圆方树的板子，但是我先做了这个。建议别做，太毒了。

题意就是给你一颗仙人掌，给定 q 个询问，让你在 O((q + n) \log n) 的复杂度级别求两点在仙人掌上的最短路。

我们可以建出圆方树：

此时我们可以钦定一个根节点，并与处理出每个环的环上的边的权值和和每个环从深度最小的点按一个顺序的边权前缀和。

既然求最短路，那就要有边权。我们发现，我们只需要将两个割点之间的距离赋值给圆方树上的边即可。那要赋给哪些边呢？我们将这个路径长度传给“深度小的节点是方点，深度大的节点是圆点”的边。剩下的“深度小的节点是圆点，深度大的节点是方点”的边全部赋值为0。最后做一个边权的前缀和，我们的预处理大概就结束了。

如图：

最后，我们处理询问。若两点的LCA是圆点，则：

那可真是太好了！我们的顶端节点固定了，直接差分一下即可。

如果方点是LCA，则：

那就有点麻烦了，会有两条路径。我们要取较小的那条。这时候我们就要用到刚刚预处理的“每个环从深度最小的点按一个顺序的边权前缀和”了，我们用她可以求出任意在环上的两点环上的距离。

代码