前言
圆方树学习笔记，从一道例题讲起。
题目链接：Hydro & bzoj。
题意简述
仙人掌上求两点距离。
题目分析
为了把仙人掌的性质发挥出来，考虑将其变成一棵树。圆方树就是这样转换的工具。
先讲讲圆方树的概念：原图上的点为圆点，每个点双对应一个方点，树边都是方点连向点双内的圆点。
具体代码实现也十分简单，就是在 tarjan 求点双的时候，弹栈的时候，新建结点，并和点双内的点连边即可。或者在处理最后连边即可。
注意，对于孤立点的处理，是保持原样不动，还是变为一对方点和圆点，视情况讨论。以下代码按照上述定义，即对于孤立点，在圆方树上体现为一对方点和白点。
void tarjan(int now, int fa){
dfn[now] = low[now] = ++timer, stack[++top] = now;
int son = 0;
for (int i = head[now]; i; i = edge[i].nxt){
int to = edge[i].to;
if (!dfn[to]){
tarjan(to, now), low[now] = min(low[now], low[to]), ++son;
if (low[to] >= dfn[now]){
scc[++scc_cnt].push_back(now);
do scc[scc_cnt].push_back(stack[top--]) while (stack[top + 1] != to);
}
} else if (to != fa) low[now] = min(low[now], dfn[to]);
}
if (!son && !fa) scc[++scc_cnt].push_back(now);
}
for (int i = 1; i <= scc_cnt; ++i)
for (const auto& u: scc[i]) {
yzh.add(i + n, u);
yzh.add(u, i + n);
}
void tarjan(int now, int fa){
dfn[now] = low[now] = ++timer, stack[++top] = now;
int son = 0;
for (int i = head[now]; i; i = edge[i].nxt){
int to = edge[i].to;
if (!dfn[to]){
tarjan(to, now), low[now] = min(low[now], low[to]), ++son;
if (low[to] >= dfn[now]){
++scc_cnt;
yzh.add(now, scc_cnt + n);
yzh.add(scc_cnt + n, now);
do {
int u = stack[top--];
yzh.add(u, scc_cnt + n);
yzh.add(scc_cnt + n, u);
} while (stack[top + 1] != to);
}
} else if (to != fa) low[now] = min(low[now], dfn[to]);
}
if (!son && !fa) {
++scc_cnt;
yzh.add(now, scc_cnt + n);
yzh.add(scc_cnt + n, now);
}
}
注意到，有时候，我们需要根据题意记录树边的边权。就比如例题。
思考我们建出树的意义是什么——原仙人掌上，不好求两点间的距离，而在树上，我们可以轻松利用 LCA 等方法求得两点间的距离。所以树的边权应该和距离有关。
我们发现，仙人掌中，原来的环都变成了菊花。原图上的距离是环上的最短距离，而在树上是从花瓣到花心，再从花心到花瓣。这样似乎没看出些什么。我们不妨把比较特殊的 LCA 处放在最后讨论，接下来只考虑往上跳 LCA 的过程。
发现，只会存在花瓣到花心，再到花顶端的那个花瓣。我们不妨设花心到顶端花瓣的距离为 \(0\)，而其余花瓣到花心的距离设置成原图环上到顶点的距离。这样就可以很好转化边权了。
至于 LCA 处，也很简单。如果 LCA 是圆点，那么不用处理；反之是方点，就要算其对应的原图上环的两点间的距离，这两点是来自询问两点不超过 LCA 的最浅祖先。这很好理解。
其实分析到这里，代码已经可以打出来了，但是在建树的时候注意如何优雅地处理边权，并精简代码。
那么再来模一模样例加深印象。
这里加粗的是原图的圆点，其他是方点。左图是圆仙人掌，右图是建出来的圆方树。
\(\operatorname{dist}(5, 7)\)：由于 \(\operatorname{LCA}(5, 7) = 1\) 是圆点，所以直接路径和相加，即 \(\operatorname{dist}(5, 7) = 3 + 0 + 1 + 0 + 2 + 0 = 6\)。
\(\operatorname{dist}(4, 8)\)：由于 \(\operatorname{LCA}(4, 8) = 14\) 是方点，所以要先跳到差一步到 \(14\) 的地方，即 \(4\) 和 \(3\)，环上距离为 \(\min \lbrace 1, 4 - 1 \rbrace = 1\)，\(\operatorname{dist}(4, 8) = 2 + 0 + 1 + 0 + 1 = 4\)。
代码
略去了快读快写，使用树剖求树上距离、LCA、和跳 father。
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
struct Graph{
struct node{
int to, nxt, len;
} edge[1000010 << 1];
int eid = 1, head[20010];
inline void add(int u, int v, int w){
edge[++eid] = {v, head[u], w};
head[u] = eid;
}
inline node & operator [] (const int x){
return edge[x];
}
} xym, yzh;
int n, m, q;
int dfn[20010], low[20010], timer, cnt;
int dis[20010], re[20010];
int sum[20010], stack[20010], stop;
bool onleft[20010];
void tarjan(int now, int fr) {
dfn[now] = low[now] = ++timer, stack[++stop] = now;
for (int i = xym.head[now], to; to = xym[i].to, i; i = xym[i].nxt) if (i ^ fr ^ 1) {
if (!dfn[to]) {
dis[to] = dis[now] + xym[i].len;
re[to] = xym[i].len; // 如果这是一条非环边，那么把它看做 now -> to -> now 的环，所以这里要设置初值
tarjan(to, i), low[now] = min(low[now], low[to]);
if (low[to] >= dfn[now]) {
++cnt, sum[cnt] = re[stack[stop]] + dis[stack[stop]] - dis[now]; // 记录环的总长
yzh.add(cnt, now, 0), yzh.add(now, cnt, 0);
do {
int u = stack[stop--];
int len = min(dis[u] - dis[now], sum[cnt] - dis[u] + dis[now]);
onleft[u] = len == dis[u] - dis[now];
yzh.add(u, cnt, len);
yzh.add(cnt, u, len);
} while (stack[stop + 1] != to);
}
} else if (dfn[to] < dfn[now]) {
re[now] = xym[i].len; // 环的闭环那条边的长度
low[now] = min(low[now], dfn[to]);
}
}
}
int siz[20010], top[20010], son[20010];
int line[20010], tfa[20010], dpt[20010];
void dfs(int now, int fa) {
tfa[now] = fa, siz[now] = 1, dpt[now] = dpt[fa] + 1;
for (int i = yzh.head[now], to; to = yzh[i].to, i; i = yzh[i].nxt) {
if (to == fa) continue;
dis[to] = dis[now] + yzh[i].len;
dfs(to, now), siz[now] += siz[to];
if (siz[to] > siz[son[now]]) son[now] = to;
}
}
void redfs(int now, int tp) {
line[dfn[now] = ++timer] = now;
top[now] = tp;
if (son[now]) redfs(son[now], tp);
for (int i = yzh.head[now], to; to = yzh[i].to, i; i = yzh[i].nxt) {
if (to == tfa[now]) continue;
if (to == son[now]) continue;
redfs(to, to);
}
}
inline int lca(int u, int v) {
while (top[u] != top[v]) {
if (dpt[top[u]] < dpt[top[v]]) swap(u, v);
u = tfa[top[u]];
}
if (dpt[u] < dpt[v]) swap(u, v);
return v;
}
inline int jump(int now, int ed) {
int res = 0;
while (top[now] != top[ed])
res = top[now], now = tfa[top[now]];
return now == ed ? res : line[dfn[ed] + 1];
}
inline int query(int u, int v) {
int p = lca(u, v);
if (p <= n)
return dis[u] + dis[v] - 2 * dis[p];
int fu = jump(u, p), fv = jump(v, p);
int d1 = dis[fu] - dis[p], d2 = dis[fv] - dis[p];
if (!onleft[fu]) d1 = sum[p] - d1;
if (!onleft[fv]) d2 = sum[p] - d2;
return dis[u] - dis[fu] + dis[v] - dis[fv] + min(abs(d1 - d2), sum[p] - abs(d1 - d2));
}
signed main() {
fread(buf, 1, MAX, stdin);
read(n), read(m), read(q);
for (int i = 1, u, v, w; i <= m; ++i) {
read(u), read(v), read(w);
xym.add(u, v, w);
xym.add(v, u, w);
}
cnt = n;
for (int i = 1; i <= n; ++i) if (!dfn[i]) tarjan(i, 0);
timer = dis[1] = 0, dfs(1, 0), redfs(1, 1);
for (int i = 1, u, v; i <= q; ++i) {
read(u), read(v);
write(query(u, v)), putchar('\n');
}
fwrite(obuf, 1, o - obuf, stdout);
return 0;
}
后记
不用圆方树亦可解此题，但是要多一些讨论、不如圆方树的直观。据说圆方树能在一般无向图上使用？我太蒻了啊。