圆方树
|
100
|
0
|
笔记

1278 字
|
24 分钟

众所周知，对于一些树上问题，可以用树形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 、树剖来解决很多问题。让我们通过几道例题来了解圆方树的应用：

P5236 【模板】静态仙人掌

题意很简单，求仙人掌图中两点间的最短路。

如何解决这个问题呢？我们可以在建树的时候引入边权，将圆-方边的边权设为 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;
}

CF 487E Tourists

求图上两点路径上的最小点权，并且带修。

容易看出使用树剖很好解决。那么怎么将图转化为树呢？一个显而易见的思路是，将方点的点权设为环上所有点的最小点权，并用一个 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);
        }
    }
}
你刚刚浪费了人生中宝贵的几分钟。
tarjan图论圆方树
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																				
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇

                    

                    
			        推荐文章
		            

		            

							
Dart/Flutter学习笔记02(初试Flutter)

							
							

							
Flutter学习笔记07：按钮

							
							

							
Dart/Flutter学习笔记04

							
							

							
Flutter学习笔记06：动态网格

							
							

							
Dart/Flutter学习笔记01

							
							

							
Flutter学习笔记05：动态列表

							
							

							
Dart/Flutter学习笔记03

							
							

							
Flutter实战——轻量级笔记应用

							
							

							
C++关系运算符重载和sort函数的结合

							
							

							
脚本合集（个人记录帖）