本文最后更新于 49 天前，其中的信息可能已经有所发展或是发生改变。
众所周知，对于一些树上问题，可以用树形DP、树链剖分等算法解决，然而图上的问题则往往更加复杂。但在一些情况下，我们可以使用圆方树将图上问题转化为树上问题（大部分时候用于处理仙人掌图上的问题）。
建树
在一张连通的无向图中，对于两个点 u 和 v，如果无论删去哪个点（只能删去一个，且不能删 u 和 v 自己）都不能使它们不连通，我们就说 u 和 v 点双连通 。
对于一个无向图中的 极大 点双连通的子图，我们称这个子图为一个 点双连通分量 。
仙人掌图 即每条边最多在一个点双连通分量中的图，或者说一条边至多只出现在一条简单回路里的图。那么圆方树如何将仙人掌图转化为树呢？我们定义原图中的节点均为 圆点 ，并在每个点双中间建立一个 方点 ，随后连接圆点建立新图，新图就是一棵树，即圆方树。
对于一个仙人掌图，我们可以采取类似求割点的方式，用 tarjan 找点双。如果在 dfs 回溯后 low[v] = dfn[u] ，则找到了一个点双，建立新点，并在新图中向点双中的所有点连边。
cnt = n;
auto tarjan = [&](auto &&self, int u) -> void {
pos++;
dfn[u] = pos;
low[u] = pos;
st.push(u);
for (int v: G[u]) {
if (!dfn[v]) {//未被访问过
self(self, v);
low[u] = min(low[u], low[v]);//回溯 low
if (low[v] == dfn[u]) {//找到一个点双
cnt++;//新建方点，序号从 n+1 开始，用于识别方点和圆点
V[u].push_back(cnt);
V[cnt].push_back(u);
while (true) {
int top = st.top();
st.pop();
V[top].push_back(cnt);
V[cnt].push_back(top);
if (top == v)break;
}
}
} else low[u] = min(low[u], dfn[v]);//注意对于访问过的点，使用 dfn[v] 而不是 low[v] 进行更新
}
}这样我们就完成了建树工作。
应用
圆方树可以结合 DP 、树剖来解决很多问题。让我们通过几道例题来了解圆方树的应用：
题意很简单，求仙人掌图中两点间的最短路。
如何解决这个问题呢？我们可以在建树的时候引入边权，将圆-方边的边权设为 0 ，方-圆边的边权设为这个环的根到目标圆点的环上最短距离。为什么要这样设呢？因为这样我们在走树边的时候，就能自动走环上的最短路，然后就可以直接用倍增求出距离，即最短路。
void tarjan(int u, int W) {//W为dfs走过的距离
pos++;
dfn[u] = pos;
low[u] = pos;
st.emplace(u, W);//将W也一起入栈
for (auto i: G[u]) {
int v = i.first, w = i.second;
if (!dfn[v]) {
tarjan(v, W + w);
low[u] = min(low[u], low[v]);
if (low[v] == dfn[u]) {
cnt++;
sum[cnt] = mp[st.top().first] + st.top().second - W;//sum是整个环的边权和，mp用于记录返祖边。则sum=栈顶点的返祖边边权+栈顶点的W-环根的W
V[u].emplace_back(cnt, 0);
V[cnt].emplace_back(u, 0);
while (true) {
int top = st.top().first;
int ww = st.top().second;
st.pop();
f[top] = ww - W;//f用于记录环上距离前缀和
V[top].emplace_back(cnt, 0);
V[cnt].emplace_back(top, min(ww - W, sum[cnt] - ww + W));//方-圆边的边权设为环上最短路
if (top == v)break;
}
}
} else {
low[u] = min(low[u], dfn[v]);
if (low[u] > low[v])mp[u] = w;//如果low[u]>low[v]，则该边为返祖边，在仙人掌图中，每个点仅有一条返祖边
}
}
}随后就可以用倍增轻松求出距离。注意，如果 u 和 v 的 lca 是方点，则还要考虑该环上的情况，这就是为什么要记录 sum 和 f。
int lca(int x, int y) {
if (dep[x] < dep[y])swap(x, y);
int d = dep[x] - dep[y], tmp = 0, res = 0;
while (d) {
if (d % 2) {
res += pre[x][tmp];
x = up[x][tmp];
}
d /= 2;
tmp++;
}
if (x == y)return res;
for (int i = 19; i >= 0; i--)
if (up[x][i] != up[y][i]) {
res += pre[x][i] + pre[y][i];
x = up[x][i];
y = up[y][i];
}
if (up[x][0] > n) {//祖先是方点
int point = up[x][0];
res += min(abs(f[x] - f[y]), sum[point] - abs(f[x] - f[y]));//对于该环上的两点，取顺逆时针中距离较短的
} else res += pre[x][0] + pre[y][0];
return res;
}求图上两点路径上的最小点权，并且带修。
容易看出使用树剖很好解决。那么怎么将图转化为树呢？一个显而易见的思路是，将方点的点权设为环上所有点的最小点权，并用一个 multiset 维护。但是假如涉及修改，就要修改所有与当前点相连的方点，效率太低。所以我们优化一下，每个方点只维护自己子节点的最小点权，那么修改的时候只需要修改父方点就好了。注意如果查询时 lca 为方点，需要再与环根（即方点的父圆点）取 min。
建树：
low[1] = 0;
auto tarjan = [&](auto &&self, int u) -> void {
pos++;
dfn[u] = pos;
if (u > 1)low[u] = pos;
st.push(u);
for (auto i: G[u]) {
if (!dfn[i]) {
self(self, i);
low[u] = min(low[u], low[i]);
if (low[i] == dfn[u]) {
cnt++;
v[u].push_back(cnt);
v[cnt].push_back(u);
while (true) {
int top = st.top();
st.pop();
v[top].push_back(cnt);
v[cnt].push_back(top);
s[cnt].insert(b[top]);//将子节点插入set
if (top == i)break;
}
b[cnt] = *s[cnt].begin();//将方点点权设为子节点最小点权
}
} else low[u] = min(low[u], dfn[i]);
}
};修改：
void update(int x, int w) {
if (x == 1) {
a[1] = w;
tree.modify(1, w);
return;
}
//修改set
s[fa[x]].erase(s[fa[x]].find(a[dfsn[x]]));
s[fa[x]].insert(w);
a[dfsn[x]] = w;
tree.modify(dfsn[fa[x]], *s[fa[x]].begin());//修改方点点权
tree.modify(dfsn[x], w);//修改圆点点权
}查询：
i64 query_path(int x, int y) {
i64 ans = 1e9 + 5;
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]])std::swap(x, y);
ans = min(ans, tree.rangeQuery(dfsn[top[x]], dfsn[x] + 1)->min);
x = fa[top[x]];
}
if (dep[x] > dep[y])std::swap(x, y);
ans = min(ans, tree.rangeQuery(dfsn[x], dfsn[y] + 1)->min);
if (x > n) {//如果lca是方点，与环根点权取min
ans = min(ans, 1LL * a[dfsn[fa[x]]]);
}
return ans;
}完整代码：
#include<bits/stdc++.h>
using i64 = long long;
using namespace std;
template<class Info, class Tag>
class LazySegmentTree {
int n;
std::vector<Info> info;
std::vector<Tag> tag;
void apply(int p, int l, int r, Tag const &v) {
info[p].apply(v, l, r);
tag[p].apply(v, l, r);
}
void push(int p, int l, int r) {
int m = (l + r) >> 1;
apply(p << 1, l, m, tag[p]);
apply(p << 1 | 1, m, r, tag[p]);
tag[p] = Tag();
}
void pull(int p, int l, int r) {
int m = (l + r) >> 1;
info[p] = Info::merge(info[p << 1], info[p << 1 | 1], l, m, m, r);
}
void modify(int p, int l, int r, int x, Info const &v) {
if (r - l == 1 && (info[p] = v, 1)) return;
int m = (l + r) >> 1;
push(p, l, r);
if (x < m) modify(p << 1, l, m, x, v);
else modify(p << 1 | 1, m, r, x, v);
pull(p, l, r);
}
std::optional<Info> rangeQuery(int p, int l, int r, int x, int y) {
if (l >= y || r <= x) return std::nullopt;
if (l >= x && r <= y) return info[p];
int m = (l + r) / 2;
push(p, l, r);
auto lres = rangeQuery(p << 1, l, m, x, y);
auto rres = rangeQuery(p << 1 | 1, m, r, x, y);
if (!lres) return rres;
if (!rres) return lres;
return Info::merge(*lres, *rres, l, m, m, r);
}
void rangeApply(int p, int l, int r, int x, int y, Tag const &v) {
if (l >= y || r <= x) return;
if (l >= x && r <= y && (apply(p, l, r, v), 1)) return;
int m = (l + r) / 2;
push(p, l, r);
rangeApply(p << 1, l, m, x, y, v);
rangeApply(p << 1 | 1, m, r, x, y, v);
pull(p, l, r);
}
template<class F, bool REV>
int find(int p, int l, int r, int x, int y, F &&pred) {
if (l >= y || r <= x || !pred(l, r, info[p])) return -1;
if (r - l == 1) return l;
int m = (l + r) / 2;
push(p, l, r);
int res = REV ? find<F, REV>(p << 1 | 1, m, r, x, y, std::forward<F>(pred))
: find<F, REV>(p << 1, l, m, x, y, std::forward<F>(pred));
if (~res) return res;
return REV ? find<F, REV>(p << 1, l, m, x, y, std::forward<F>(pred))
: find<F, REV>(p << 1 | 1, m, r, x, y, std::forward<F>(pred));
}
public:
LazySegmentTree() : n(0) {
}
LazySegmentTree(int n_, Info v_ = Info()) {
init(n_, v_);
}
template<class T>
LazySegmentTree(std::vector<T> init_) {
init(init_);
}
void init(int n_, Info v_ = Info()) {
init(std::vector(n_, v_));
}
template<class T>
void init(std::vector<T> init_) {
n = init_.size();
info.assign(4 << std::__lg(n), Info());
tag.assign(4 << std::__lg(n), Tag());
std::function<void(int, int, int)> build = [&](int p, int l, int r) {
if (r - l == 1 && (info[p] = init_[l], true)) return;
int m = (l + r) / 2;
build(p << 1, l, m);
build(p << 1 | 1, m, r);
pull(p, l, r);
};
build(1, 0, n);
}
void modify(int p, Info const &v) {
modify(1, 0, n, p, v);
}
std::optional<Info> rangeQuery(int l, int r) {
return rangeQuery(1, 0, n, l, r);
}
void rangeApply(int l, int r, const Tag &v) {
return rangeApply(1, 0, n, l, r, v);
}
template<class F>
int findFirst(int l, int r, F &&pred) {
return find<F, false>(1, 0, n, l, r, std::forward<F>(pred));
}
template<class F>
int findLast(int l, int r, F &&pred) {
return find<F, true>(1, 0, n, l, r, std::forward<F>(pred));
}
};
struct Tag {
void apply(Tag const &t, int l, int r) {
}
};
struct Info {
i64 min = 1e9 + 5;
Info() = default;
Info(i64 min_) : min(min_) {}
void apply(Tag const &t, int l, int r) {
}
static Info merge(Info const &a, Info const &b, int la, int ra, int lb, int rb) {
return std::min(a.min, b.min);
}
};
const int N = 200005;
vector<vector<int>> G, v;
vector<int> a, b, dfn, low, fa, dep, sz, hson, top, dfsn, rdfn;
stack<int> st;
vector<multiset<int>> s;
int cnnt = 0, n;
LazySegmentTree<Info, Tag> tree;
void dfs1(int u, int f = 0) {
fa[u] = f, sz[u] = 1, dep[u] = dep[f] + 1;
for (auto i: v[u])
if (i != f) {
dfs1(i, u);
sz[u] += sz[i];
if (sz[i] > sz[hson[u]])hson[u] = i;
}
}
void dfs2(int x, int f = 0) {
dfsn[x] = ++cnnt;
if (hson[x] != 0) {
top[hson[x]] = top[x];
dfs2(hson[x], x);
}
for (auto i: v[x])
if (i != f && !top[i]) {
top[i] = i;
dfs2(i, x);
}
rdfn[x] = cnnt;
}
i64 query_path(int x, int y) {
i64 ans = 1e9 + 5;
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]])std::swap(x, y);
ans = min(ans, tree.rangeQuery(dfsn[top[x]], dfsn[x] + 1)->min);
x = fa[top[x]];
}
if (dep[x] > dep[y])std::swap(x, y);
ans = min(ans, tree.rangeQuery(dfsn[x], dfsn[y] + 1)->min);
if (x > n) {
ans = min(ans, 1LL * a[dfsn[fa[x]]]);
}
return ans;
}
void update(int x, int w) {
if (x == 1) {
a[1] = w;
tree.modify(1, w);
return;
}
s[fa[x]].erase(s[fa[x]].find(a[dfsn[x]]));
s[fa[x]].insert(w);
a[dfsn[x]] = w;
tree.modify(dfsn[fa[x]], *s[fa[x]].begin());
tree.modify(dfsn[x], w);
}
int main() {
G.resize(N), v.resize(N);
a.resize(N), b.resize(N), dfn.resize(N), low.resize(N);
fa.resize(N), dep.resize(N), sz.resize(N), hson.resize(N);
top.resize(N), dfsn.resize(N), rdfn.resize(N);
s.resize(N);
int m, q, cnt, pos = 0;
cin >> n >> m >> q;
cnt = n;
for (int i = 1; i <= n; i++)cin >> b[i];
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
low[1] = 0;
auto tarjan = [&](auto &&self, int u) -> void {
pos++;
dfn[u] = pos;
if (u > 1)low[u] = pos;
st.push(u);
for (auto i: G[u]) {
if (!dfn[i]) {
self(self, i);
low[u] = min(low[u], low[i]);
if (low[i] == dfn[u]) {
cnt++;
v[u].push_back(cnt);
v[cnt].push_back(u);
while (true) {
int top = st.top();
st.pop();
v[top].push_back(cnt);
v[cnt].push_back(top);
s[cnt].insert(b[top]);
if (top == i)break;
}
b[cnt] = *s[cnt].begin();
}
} else low[u] = min(low[u], dfn[i]);
}
};
tarjan(tarjan, 1);
dfs1(1);
top[1] = 1;
dfs2(1);
for (int i = 1; i <= cnt; i++) {
a[dfsn[i]] = b[i];
}
tree.init(a);
while (q--) {
char op;
int l, r;
std::cin >> op >> l >> r;
if (op == 'A') {
std::cout << query_path(l, r) << '\n';
} else {
update(l, r);
}
}
}
