cp-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub Hoshinonono/cp-library

:heavy_check_mark: 最小共通祖先 (LCA, Lowest Common Ancestor) (タブリング)
(Tree/lca_doubling.hpp)

概要

構築 $\text{O}(N\log N)$ 、クエリ $\text{O}(\log N)$ で最小共通祖先 (Lowest Common Ancestor) を習得できるライブラリである。
実装はDFSの行きがけ順のみを使用していて場合分けを簡潔にしている。

関数名など 機能 計算量
LCA_tree(std::vector<std::vector<int>> G, int root) root を根とする LCA のダブリングテーブルを構築する。
・第1引数には無向辺の木もしくは根付き木を G としてコンストラクタに渡す。
・第2引数は根を指定する(省略可能)。省略した場合 0 を根とする。		 $\text{O}(N\log N)$
int lca(int u, int v) 頂点 $u$ と頂点 $v$ のLCAを返す。 $\text{O}(\log N)$
(1) int la(int v, int d)
(2) int la(int from, int to, int d) 		(1)頂点 $v$ から根に向かって距離 $d$ 進んだ頂点を返す。
(2)頂点 $\text{from}$ から頂点 $\text{to}$ に向かって距離 $d$ 進んだ頂点を返す。
存在しない場合は -1 を返す。		 $\text{O}(\log N)$
int dist(int u, int v) 頂点 $u$ と頂点 $v$ の距離を出力する。 $\text{O}(\log N)$
bool on_path(int from, int to, int mid) 頂点 $\text{mid}$ が頂点 $\text{from}$ と頂点 $\text{to}$ の単純パス上にあるかを判定する。 $\text{O}(\log N)$
int Auxiliary_Tree(std::vector<int> ver) 頂点集合 $\text{ver}$ を連結にするために必要な辺の数を出力する。 頂点集合の大きさを $|S|$ として
$\text{O}(|S|\log N)$

Verified with

Code

struct LCA_tree {
    int n, LOGV, root;
    std::vector<std::vector<int>> &g, parent;
    std::vector<int> depth, id;
    LCA_tree(std::vector<std::vector<int>> &_g) : LCA_tree(_g, 0){}
    LCA_tree(std::vector<std::vector<int>> &_g, int r) : n(_g.size()), g(_g), root(r), depth(n), id(n, -1) {
        LOGV = std::__lg(std::max(1, n - 1));
        parent.resize(LOGV + 1, std::vector<int>(n, -1));
        std::vector<int> stk;
        stk.reserve(n);
        stk.emplace_back(root);
        depth[root] = 0;
        int cnt = 0;
        while(!stk.empty()){
            int v = stk.back();
            stk.pop_back();
            id[v] = cnt++;
            for(int i = 1; (1 << i) <= depth[v]; i++){
                parent[i][v] = parent[i - 1][parent[i - 1][v]];
            }
            for(auto &&u : g[v]){
                if(id[u] != -1) continue;
                parent[0][u] = v;
                depth[u] = depth[v] + 1;
                stk.emplace_back(u);
            }
        }
    }
    int lca(int u, int v){
        assert(0 <= u && u < n);
        assert(0 <= v && v < n);
        if(depth[u] > depth[v]) std::swap(u, v);
        int d = depth[v] - depth[u];
        while(d){
            v = parent[std::__lg(d & -d)][v];
            d -= d & -d;
        }
        if(u == v) return u;
        for(int i = std::__lg(depth[v]); i >= 0; i--){
            if(parent[i][u] != parent[i][v]){
                u = parent[i][u];
                v = parent[i][v];
            }
        }
        return parent[0][u];
    }
    int la(int v, int d){
        if(d > depth[v]) return -1;
        while(d){
            v = parent[std::__lg(d & -d)][v];
            d -= d & -d;
        }
        return v;
    }
    int la(int from, int to, int d){
        int lcav = lca(from, to);
        int len = depth[from] + depth[to] - 2 * depth[lcav];
        if(d > len) return -1;
        return (d <= depth[from] - depth[lcav] ? la(from, d) : la(to, len - d));
    }
    int dist(int u, int v){
        int lcav = lca(u, v);
        return depth[u] + depth[v] - 2 * depth[lcav];
    }
    bool on_path(int from, int to, int mid){
        return dist(from, mid) + dist(mid, to) == dist(from, to);
    }
    int Auxiliary_Tree(std::vector<int> &ver){
        int ret = 0, m = ver.size();
        std::sort(ver.begin(), ver.end(), [&](int va, int vb) {return id[va] < id[vb];});
        for(int i = 0; i < m; i++){
            ret += depth[ver[i]];
            ret -= depth[lca(ver[i], ver[i + 1 == m ? 0 : i + 1])];
        }
        return ret;
    }
};
#line 1 "Tree/lca_doubling.hpp"
struct LCA_tree {
    int n, LOGV, root;
    std::vector<std::vector<int>> &g, parent;
    std::vector<int> depth, id;
    LCA_tree(std::vector<std::vector<int>> &_g) : LCA_tree(_g, 0){}
    LCA_tree(std::vector<std::vector<int>> &_g, int r) : n(_g.size()), g(_g), root(r), depth(n), id(n, -1) {
        LOGV = std::__lg(std::max(1, n - 1));
        parent.resize(LOGV + 1, std::vector<int>(n, -1));
        std::vector<int> stk;
        stk.reserve(n);
        stk.emplace_back(root);
        depth[root] = 0;
        int cnt = 0;
        while(!stk.empty()){
            int v = stk.back();
            stk.pop_back();
            id[v] = cnt++;
            for(int i = 1; (1 << i) <= depth[v]; i++){
                parent[i][v] = parent[i - 1][parent[i - 1][v]];
            }
            for(auto &&u : g[v]){
                if(id[u] != -1) continue;
                parent[0][u] = v;
                depth[u] = depth[v] + 1;
                stk.emplace_back(u);
            }
        }
    }
    int lca(int u, int v){
        assert(0 <= u && u < n);
        assert(0 <= v && v < n);
        if(depth[u] > depth[v]) std::swap(u, v);
        int d = depth[v] - depth[u];
        while(d){
            v = parent[std::__lg(d & -d)][v];
            d -= d & -d;
        }
        if(u == v) return u;
        for(int i = std::__lg(depth[v]); i >= 0; i--){
            if(parent[i][u] != parent[i][v]){
                u = parent[i][u];
                v = parent[i][v];
            }
        }
        return parent[0][u];
    }
    int la(int v, int d){
        if(d > depth[v]) return -1;
        while(d){
            v = parent[std::__lg(d & -d)][v];
            d -= d & -d;
        }
        return v;
    }
    int la(int from, int to, int d){
        int lcav = lca(from, to);
        int len = depth[from] + depth[to] - 2 * depth[lcav];
        if(d > len) return -1;
        return (d <= depth[from] - depth[lcav] ? la(from, d) : la(to, len - d));
    }
    int dist(int u, int v){
        int lcav = lca(u, v);
        return depth[u] + depth[v] - 2 * depth[lcav];
    }
    bool on_path(int from, int to, int mid){
        return dist(from, mid) + dist(mid, to) == dist(from, to);
    }
    int Auxiliary_Tree(std::vector<int> &ver){
        int ret = 0, m = ver.size();
        std::sort(ver.begin(), ver.end(), [&](int va, int vb) {return id[va] < id[vb];});
        for(int i = 0; i < m; i++){
            ret += depth[ver[i]];
            ret -= depth[lca(ver[i], ver[i + 1 == m ? 0 : i + 1])];
        }
        return ret;
    }
};
Back to top page