Lowest common ancestor （最小共通祖先）
(tree/lowest_common_ancestor.hpp)

• View this file on GitHub
• Last update: 2022-07-31 01:04:01+09:00
• Include: #include "tree/lowest_common_ancestor.hpp"

根を固定した木に対する 2 頂点の最小共通祖先，および 2 頂点間の距離，$k$ 番目の親の計算．前処理 $O(N \log N)$, クエリ $O(\log N)$．

使用方法

UndirectedWeightedTree<long long> tree(N);
for (int e = 0; e < N - 1; e++) {
    int u, v, w;
    cin >> u >> v >> w;
    tree.add_edge(u, v, w);
}

tree.fix_root(0);

cout << tree.lowest_common_ancestor(a, b) << '\n'; // (a, b) の最長共通祖先
cout << tree.kth_parent(a, k) << '\n';  // 頂点 a の k 世代親
cout << tree.path_length(a, b) << '\n'; // 2 頂点 a, b の距離

問題例

• Library Checker: Lowest Common Ancestor
• yukicoder No.898 tri-βutree

Verified with

• tree/test/jump_on_tree.test.cpp
• tree/test/lca.test.cpp
• tree/test/lca.yuki898.test.cpp

Code

#pragma once
#include <utility>
#include <vector>

// CUT begin
// lowest common ancestor (LCA) for undirected weighted tree
template <typename T> struct UndirectedWeightedTree {
    int INVALID = -1;
    int V, lgV;
    int E;
    int root;
    std::vector<std::vector<std::pair<int, int>>> adj; // (nxt_vertex, edge_id)
    // vector<pint> edge; // edges[edge_id] = (vertex_id, vertex_id)
    std::vector<T> weight;     // w[edge_id]
    std::vector<int> par;      // parent_vertex_id[vertex_id]
    std::vector<int> depth;    // depth_from_root[vertex_id]
    std::vector<T> acc_weight; // w_sum_from_root[vertex_id]

    void _fix_root_dfs(int now, int prv, int prv_edge_id) {
        par[now] = prv;
        if (prv_edge_id != INVALID) acc_weight[now] = acc_weight[prv] + weight[prv_edge_id];
        for (auto nxt : adj[now])
            if (nxt.first != prv) {
                depth[nxt.first] = depth[now] + 1;
                _fix_root_dfs(nxt.first, now, nxt.second);
            }
    }

    UndirectedWeightedTree() = default;
    UndirectedWeightedTree(int N) : V(N), E(0), adj(N) {
        lgV = 1;
        while (1 << lgV < V) lgV++;
    }

    void add_edge(int u, int v, T w) {
        adj[u].emplace_back(v, E);
        adj[v].emplace_back(u, E);
        // edge.emplace_back(u, v);
        weight.emplace_back(w);
        E++;
    }

    std::vector<std::vector<int>> doubling;
    void _doubling_precalc() {
        doubling.assign(lgV, std::vector<int>(V));
        doubling[0] = par;
        for (int d = 0; d < lgV - 1; d++)
            for (int i = 0; i < V; i++) {
                if (doubling[d][i] == INVALID)
                    doubling[d + 1][i] = INVALID;
                else
                    doubling[d + 1][i] = doubling[d][doubling[d][i]];
            }
    }

    void fix_root(int r) {
        root = r;
        par.resize(V);
        depth.resize(V);
        depth[r] = 0;
        acc_weight.resize(V);
        acc_weight[r] = 0;
        _fix_root_dfs(root, INVALID, INVALID);
        _doubling_precalc();
    }

    int kth_parent(int x, int k) const {
        if (depth[x] < k) return INVALID;
        for (int d = 0; d < lgV; d++) {
            if (x == INVALID) return INVALID;
            if (k & (1 << d)) x = doubling[d][x];
        }
        return x;
    }

    int lowest_common_ancestor(int u, int v) const {
        if (depth[u] > depth[v]) std::swap(u, v);

        v = kth_parent(v, depth[v] - depth[u]);
        if (u == v) return u;
        for (int d = lgV - 1; d >= 0; d--) {
            if (doubling[d][u] != doubling[d][v]) u = doubling[d][u], v = doubling[d][v];
        }
        return par[u];
    }

    T path_length(int u, int v) const {
        // Not distance, but the sum of weights
        int r = lowest_common_ancestor(u, v);
        return (acc_weight[u] - acc_weight[r]) + (acc_weight[v] - acc_weight[r]);
    }

    int s_to_t_by_k_steps(int s, int t, int k) const {
        int l = lowest_common_ancestor(s, t);
        int dsl = depth[s] - depth[l], dtl = depth[t] - depth[l];
        if (k > dsl + dtl) {
            return INVALID;
        } else if (k < dsl) {
            return kth_parent(s, k);
        } else if (k == dsl) {
            return l;
        } else {
            return kth_parent(t, dsl + dtl - k);
        }
    }
};

#line 2 "tree/lowest_common_ancestor.hpp"
#include <utility>
#include <vector>

// CUT begin
// lowest common ancestor (LCA) for undirected weighted tree
template <typename T> struct UndirectedWeightedTree {
    int INVALID = -1;
    int V, lgV;
    int E;
    int root;
    std::vector<std::vector<std::pair<int, int>>> adj; // (nxt_vertex, edge_id)
    // vector<pint> edge; // edges[edge_id] = (vertex_id, vertex_id)
    std::vector<T> weight;     // w[edge_id]
    std::vector<int> par;      // parent_vertex_id[vertex_id]
    std::vector<int> depth;    // depth_from_root[vertex_id]
    std::vector<T> acc_weight; // w_sum_from_root[vertex_id]

    void _fix_root_dfs(int now, int prv, int prv_edge_id) {
        par[now] = prv;
        if (prv_edge_id != INVALID) acc_weight[now] = acc_weight[prv] + weight[prv_edge_id];
        for (auto nxt : adj[now])
            if (nxt.first != prv) {
                depth[nxt.first] = depth[now] + 1;
                _fix_root_dfs(nxt.first, now, nxt.second);
            }
    }

    UndirectedWeightedTree() = default;
    UndirectedWeightedTree(int N) : V(N), E(0), adj(N) {
        lgV = 1;
        while (1 << lgV < V) lgV++;
    }

    void add_edge(int u, int v, T w) {
        adj[u].emplace_back(v, E);
        adj[v].emplace_back(u, E);
        // edge.emplace_back(u, v);
        weight.emplace_back(w);
        E++;
    }

    std::vector<std::vector<int>> doubling;
    void _doubling_precalc() {
        doubling.assign(lgV, std::vector<int>(V));
        doubling[0] = par;
        for (int d = 0; d < lgV - 1; d++)
            for (int i = 0; i < V; i++) {
                if (doubling[d][i] == INVALID)
                    doubling[d + 1][i] = INVALID;
                else
                    doubling[d + 1][i] = doubling[d][doubling[d][i]];
            }
    }

    void fix_root(int r) {
        root = r;
        par.resize(V);
        depth.resize(V);
        depth[r] = 0;
        acc_weight.resize(V);
        acc_weight[r] = 0;
        _fix_root_dfs(root, INVALID, INVALID);
        _doubling_precalc();
    }

    int kth_parent(int x, int k) const {
        if (depth[x] < k) return INVALID;
        for (int d = 0; d < lgV; d++) {
            if (x == INVALID) return INVALID;
            if (k & (1 << d)) x = doubling[d][x];
        }
        return x;
    }

    int lowest_common_ancestor(int u, int v) const {
        if (depth[u] > depth[v]) std::swap(u, v);

        v = kth_parent(v, depth[v] - depth[u]);
        if (u == v) return u;
        for (int d = lgV - 1; d >= 0; d--) {
            if (doubling[d][u] != doubling[d][v]) u = doubling[d][u], v = doubling[d][v];
        }
        return par[u];
    }

    T path_length(int u, int v) const {
        // Not distance, but the sum of weights
        int r = lowest_common_ancestor(u, v);
        return (acc_weight[u] - acc_weight[r]) + (acc_weight[v] - acc_weight[r]);
    }

    int s_to_t_by_k_steps(int s, int t, int k) const {
        int l = lowest_common_ancestor(s, t);
        int dsl = depth[s] - depth[l], dtl = depth[t] - depth[l];
        if (k > dsl + dtl) {
            return INVALID;
        } else if (k < dsl) {
            return kth_parent(s, k);
        } else if (k == dsl) {
            return l;
        } else {
            return kth_parent(t, dsl + dtl - k);
        }
    }
};

Back to top page