cp-library
C++ Library for Competitive Programming
最小共通祖先 (lowest common ancestor) ダブリング版
(include/emthrm/graph/tree/lowest_common_ancestor_by_doubling.hpp)
- View this file on GitHub
- Last update: 2023-05-12 15:57:02+09:00
- Include:
#include "emthrm/graph/tree/lowest_common_ancestor_by_doubling.hpp"
最小共通祖先 (lowest common ancestor)
根付き木のある2頂点に対して最も深い共通祖先である。
時間計算量
| 時間計算量 | |
|---|---|
| ダブリング版 | $\langle O(\lvert V \rvert \log{\lvert V \rvert}), O(\log{\lvert V \rvert}) \rangle$ |
| Euler tour technique 版 | $\langle O(\lvert V \rvert \log{\lvert V \rvert}), O(1) \rangle$ |
仕様
ダブリング版
template <typename CostType>
struct LowestCommonAncestorByDoubling;
-
CostType：辺のコストを表す型
メンバ変数
| 名前 | 説明 | 備考 |
|---|---|---|
std::vector<int> depth |
depth[i] は頂点 $i$ の深さを表す。 |
|
std::vector<CostType> dist |
dist[i] は根と頂点 $i$ の間の距離を表す。 |
cost-free 版は depth に同じである。 |
メンバ関数
| 名前 | 効果・戻り値 | 要件 |
|---|---|---|
explicit LowestCommonAncestorByDoubling(const std::vector<std::vector<Edge<CostType>>>& graph); |
木 $\mathrm{graph}$ に対してオブジェクトを構築する。 | |
void build(const int root = 0); |
根を $\mathrm{root}$ として構築する。 | |
int query(int u, int v) const; |
頂点 $u, v$ の最小共通祖先 | |
CostType distance(const int u, const int v) const; |
頂点 $u, v$ 間の距離 | |
int level_ancestor(int v, const int d) const; |
level ancestor problem $\mathrm{LA}(v, d)$。ただし $d \leq \mathrm{depth}(v)$ でなければ $-1$ を返す。 | |
int jump(const int u, const int v, const int d) const; |
頂点 $u$ から頂点 $v$ まで距離 $d$ だけ進んだときの頂点。ただし $d > \mathrm{dist}(u, v)$ を満たすときは $-1$ を返す。 | cost-free 版 |
Euler tour technique版
template <typename CostType>
struct LowestCommonAncestor : EulerTourTechnique<CostType>;
-
CostType：辺のコストを表す型
メンバ関数
| 名前 | 効果・戻り値 |
|---|---|
explicit LowestCommonAncestor(const std::vector<std::vector<Edge<CostType>>>& graph, const int root = 0); |
根を $\mathrm{root}$ とする木 $\mathrm{graph}$ に対してオブジェクトを構築する。 |
int query(int u, int v) const; |
頂点 $u, v$ の最小共通祖先 |
heavy-light decomposition 版
参考文献
- 秋葉拓哉，岩田陽一，北川宜稔：プログラミングコンテストチャレンジブック [第2版]，pp.292-295，マイナビ出版（2012）
- https://yukicoder.me/wiki/lowest_common_ancestor
level ancestor problem
- https://en.wikipedia.org/wiki/Level_ancestor_problem
Euler tour technique 版
- Omer Berkman and Uzi Vishkin: Recursive Star-Tree Parallel Data Structure, SIAM Journal on Computing, Vol. 22, No. 2, pp. 221–242 (1993). https://doi.org/10.1137/0222017
- https://github.com/drken1215/algorithm/blob/efb8cf052b095e49e70135a6fb628308d06f49b2/DataStructureOnTree/euler_tour_on_nodes.cpp
TODO
- Tarjan’s off-line lowest common ancestors algorithm
http://www.prefield.com/algorithm/graph/least_common_ancestor.html- https://github.com/spaghetti-source/algorithm/blob/master/graph/least_common_ancestor_tarjan.cc
- http://monyone.github.io/teihen_library/#OfflineLCA
- level ancestor problem $\langle O(\lvert V \rvert), O(1) \rangle$
- https://www2.compute.dtu.dk/courses/02282/2018/levelancestor/levelancestor1x1.pdf
- https://37zigen.com/level-ancestor-problem/
- https://hdbn.hatenadiary.org/entry/20111125/1322194487
- https://drive.google.com/drive/folders/1atQRO6Y9bHgLDH-YLq3obDwMxIuk7–h
- https://noshi91.hatenablog.com/entry/2019/09/22/114149
- https://suisen-kyopro.hatenablog.com/entry/2022/04/04/043452
- https://twitter.com/GauravML/status/1415073033522319367
- https://twitter.com/keijak/status/1510953079872663555
- https://github.com/noshi91/n91lib_rs/blob/c9bd9cf36cbf4637884a049a4fe44f45b06ff71f/src/data_structure/level_ancestor.rs
Submissons
Depends on
Verified with
グラフ/二重辺連結成分分解 lowlink 版
(test/graph/2-edge-connected_components_by_lowlink.test.cpp)
グラフ/木/最小共通祖先 ダブリング版
(test/graph/tree/lowest_common_ancestor_by_doubling.test.cpp)
Code
#ifndef EMTHRM_GRAPH_TREE_LOWEST_COMMON_ANCESTOR_BY_DOUBLING_HPP_
#define EMTHRM_GRAPH_TREE_LOWEST_COMMON_ANCESTOR_BY_DOUBLING_HPP_
#include <bit>
#include <cassert>
#include <utility>
#include <vector>
#include "emthrm/graph/edge.hpp"
namespace emthrm {
template <typename CostType>
struct LowestCommonAncestorByDoubling {
std::vector<int> depth;
std::vector<CostType> dist;
explicit LowestCommonAncestorByDoubling(
const std::vector<std::vector<Edge<CostType>>>& graph)
: is_built(false), n(graph.size()),
table_h(std::countr_zero(std::bit_floor(graph.size())) + 1),
graph(graph) {
assert(n > 0);
depth.resize(n);
dist.resize(n);
parent.resize(table_h, std::vector<int>(n));
}
void build(const int root = 0) {
is_built = true;
dfs(-1, root, 0, 0);
for (int i = 0; i + 1 < table_h; ++i) {
for (int ver = 0; ver < n; ++ver) {
parent[i + 1][ver] =
(parent[i][ver] == -1 ? -1 : parent[i][parent[i][ver]]);
}
}
}
int query(int u, int v) const {
assert(is_built);
if (depth[u] > depth[v]) std::swap(u, v);
for (int i = 0; i < table_h; ++i) {
if ((depth[v] - depth[u]) >> i & 1) v = parent[i][v];
}
if (u == v) return u;
for (int i = table_h - 1; i >= 0; --i) {
if (parent[i][u] != parent[i][v]) {
u = parent[i][u];
v = parent[i][v];
}
}
return parent.front()[u];
}
CostType distance(const int u, const int v) const {
assert(is_built);
return dist[u] + dist[v] - dist[query(u, v)] * 2;
}
int level_ancestor(int v, const int d) const {
assert(is_built);
if (depth[v] < d) return -1;
for (int i = depth[v] - d, bit = 0; i > 0; i >>= 1, ++bit) {
if (i & 1) v = parent[bit][v];
}
return v;
}
private:
bool is_built;
const int n, table_h;
std::vector<std::vector<int>> parent;
const std::vector<std::vector<Edge<CostType>>> graph;
void dfs(const int par, const int ver, const int cur_depth,
const CostType cur_dist) {
depth[ver] = cur_depth;
dist[ver] = cur_dist;
parent.front()[ver] = par;
for (const Edge<CostType>& e : graph[ver]) {
if (e.dst != par) dfs(ver, e.dst, cur_depth + 1, cur_dist + e.cost);
}
}
};
} // namespace emthrm
#endif // EMTHRM_GRAPH_TREE_LOWEST_COMMON_ANCESTOR_BY_DOUBLING_HPP_#line 1 "include/emthrm/graph/tree/lowest_common_ancestor_by_doubling.hpp"
#include <bit>
#include <cassert>
#include <utility>
#include <vector>
#line 1 "include/emthrm/graph/edge.hpp"
/**
* @title 辺
*/
#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_
#include <compare>
namespace emthrm {
template <typename CostType>
struct Edge {
CostType cost;
int src, dst;
explicit Edge(const int src, const int dst, const CostType cost = 0)
: cost(cost), src(src), dst(dst) {}
auto operator<=>(const Edge& x) const = default;
};
} // namespace emthrm
#endif // EMTHRM_GRAPH_EDGE_HPP_
#line 10 "include/emthrm/graph/tree/lowest_common_ancestor_by_doubling.hpp"
namespace emthrm {
template <typename CostType>
struct LowestCommonAncestorByDoubling {
std::vector<int> depth;
std::vector<CostType> dist;
explicit LowestCommonAncestorByDoubling(
const std::vector<std::vector<Edge<CostType>>>& graph)
: is_built(false), n(graph.size()),
table_h(std::countr_zero(std::bit_floor(graph.size())) + 1),
graph(graph) {
assert(n > 0);
depth.resize(n);
dist.resize(n);
parent.resize(table_h, std::vector<int>(n));
}
void build(const int root = 0) {
is_built = true;
dfs(-1, root, 0, 0);
for (int i = 0; i + 1 < table_h; ++i) {
for (int ver = 0; ver < n; ++ver) {
parent[i + 1][ver] =
(parent[i][ver] == -1 ? -1 : parent[i][parent[i][ver]]);
}
}
}
int query(int u, int v) const {
assert(is_built);
if (depth[u] > depth[v]) std::swap(u, v);
for (int i = 0; i < table_h; ++i) {
if ((depth[v] - depth[u]) >> i & 1) v = parent[i][v];
}
if (u == v) return u;
for (int i = table_h - 1; i >= 0; --i) {
if (parent[i][u] != parent[i][v]) {
u = parent[i][u];
v = parent[i][v];
}
}
return parent.front()[u];
}
CostType distance(const int u, const int v) const {
assert(is_built);
return dist[u] + dist[v] - dist[query(u, v)] * 2;
}
int level_ancestor(int v, const int d) const {
assert(is_built);
if (depth[v] < d) return -1;
for (int i = depth[v] - d, bit = 0; i > 0; i >>= 1, ++bit) {
if (i & 1) v = parent[bit][v];
}
return v;
}
private:
bool is_built;
const int n, table_h;
std::vector<std::vector<int>> parent;
const std::vector<std::vector<Edge<CostType>>> graph;
void dfs(const int par, const int ver, const int cur_depth,
const CostType cur_dist) {
depth[ver] = cur_depth;
dist[ver] = cur_dist;
parent.front()[ver] = par;
for (const Edge<CostType>& e : graph[ver]) {
if (e.dst != par) dfs(ver, e.dst, cur_depth + 1, cur_dist + e.cost);
}
}
};
} // namespace emthrm