圆方树

定义

圆方树：将无向图转化为树形结构的数据结构，使得树上 2 点路径上的点都是原图的必经点。

圆点：原无向图 \(G\) 中的点，仍然保留在圆方树中，称之为圆点。

方点：将每一个点双连通分量新建一个“方点”。

树边：每一个方点都向对应的点双内的圆点连边。

基本性质：

性质一：圆方树的总点数 = 原图点数 \(n\) + 点双个数 \(tot\)，上限 \(2n - 1\)。

性质二：圆点是被方点隔开的，一条边的两个端点一定是圆点和方点。

性质三：圆点的度数就是包含该点的点双个数。

性质四：圆方树删除点 \(x\) 后剩余的结点的连通性与原图中删除 \(x\) 后的连通性等价。

性质五：原图中 \(x\) 到 \(y\) 的路径的必经点就是圆方树上 \(x\) 到 \(y\) 的圆点。

性质六：圆点为割点时才有超过 1 个儿子节点。

例题

CF487E Tourists

我们可以先建出园方树，然后在每个方结点维护其子结点的最小值，然后答案就是对应路径上点的最小值，这个可以用树链剖分 + 线段树实现。

时间复杂度： \(O(n\log n\log n)\)

代码有点长

#include <bits/stdc++.h>

using namespace std;

const int N = 200010, INF = 0x3f3f3f3f;

vector<int> e1[N], e2[N];

int dfn[N], low[N], _cnt, tot;
stack<int> stk;
multiset<int> s[N];

void tarjan(int u, int fa) {
    dfn[u] = low[u] = ++_cnt;
    stk.push(u);
    for (int to : e1[u]) {
        if (!dfn[to]) {
            tarjan(to, u);
            low[u] = min(low[u], low[to]);
            if (low[to] >= dfn[u]) {
                tot++;
                int p = 0;
                do {
                    p = stk.top();
                    stk.pop();
                    e2[tot].push_back(p);
                    e2[p].push_back(tot);
                } while (p != to);
                e2[tot].push_back(u);
                e2[u].push_back(tot);
            }
        }
        else if (to != fa) low[u] = min(low[u], dfn[to]);
    }
}

int n, m, q;
int sz[N], son[N], fa[N], dep[N];
int top[N], rk[N], id[N], cnt;

void dfs1(int u, int f) {
    sz[u] = 1; dep[u] = dep[f] + 1; fa[u] = f;
    for (int to : e2[u]) {
        if (to == f) continue;
        dfs1(to, u);
        sz[u] += sz[to];
        if (sz[son[u]] < sz[to]) son[u] = to;
    }
}

void dfs2(int u, int t) {
    top[u] = t; id[u] = ++cnt, rk[cnt] = u;
    if (son[u]) dfs2(son[u], t);
    for (int to : e2[u]) {
        if (to == fa[u] || to == son[u]) continue;
        dfs2(to, to);
    }
}

void dfs3(int u) {
    for (int to : e2[u]) {
        if (to == fa[u]) continue;
        if (u > n) s[u].insert(*s[to].begin());
        dfs3(to);
    }
}

struct node {
    int min;
} tr[N << 2];

node pushup(node l, node r) {
    return {min(l.min, r.min)};
}

void init(int u, int l, int r) {
    if (l == r) {
        tr[u].min = *s[rk[l]].begin();
        return;
    }
    int mid = l + r >> 1;
    init(u << 1, l, mid);
    init(u << 1 | 1, mid + 1, r);
    tr[u] = pushup(tr[u << 1], tr[u << 1 | 1]);
}

void update(int u, int l, int r, int x) {
    if (l == r) {
        tr[u].min = *s[rk[x]].begin();
        return;
    }
    int mid = l + r >> 1;
    if (x <= mid) update(u << 1, l, mid, x);
    else update(u << 1 | 1, mid + 1, r,  x);
    tr[u] = pushup(tr[u << 1], tr[u << 1 | 1]);
}

node query(int u, int l, int r, int pl, int pr) {
    if (pl <= l && r <= pr) return tr[u];
    int mid = l + r >> 1;
    if (pr <= mid) return query(u << 1, l, mid, pl, pr);
    else if (pl > mid) return query(u << 1 | 1, mid + 1, r, pl, pr);
    else return pushup(query(u << 1, l, mid, pl, pr),  query(u << 1 | 1, mid + 1, r, pl, pr));
}

node ask(int x, int y) {
    node ans = {INF};
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        ans = pushup(ans, query(1, 1, tot, id[top[x]], id[x]));
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    ans = pushup(ans, query(1, 1, tot, id[x], id[y]));
    if (x > n) ans = pushup(ans, query(1, 1, tot, id[fa[x]], id[fa[x]]));
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        s[i].insert(x);
    }
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        e1[u].push_back(v);
        e1[v].push_back(u);
    }

    tot = n;
    tarjan(1, 1);
    dfs1(1, 1);
    dfs2(1, 1);
    dfs3(1);
    init(1, 1, tot);

    char opt;
    int x, y;
    while (q--) {
        cin >> opt >> x >> y;
        if (opt == 'C') {
            int past = *s[x].begin();
            s[x].clear();
            s[x].insert(y);
            s[fa[x]].erase(past);
            s[fa[x]].insert(y);
            update(1, 1, tot, id[x]);
            update(1, 1, tot, id[fa[x]]);
        }
        else cout << ask(x, y).min << '\n';
    }
    return 0;
}