lowest_common_ancestor.hpp¶
预处理有根树后回答两点最近公共祖先、距离和向上跳祖先；适合频繁树上定位。
Complexity: Time: O(n log n) build and O(1) LCA/ancestor queries. Space: O(n log n).
AC 记录：jump_on_tree, lca。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n log n) build and O(1) LCA/ancestor queries.
/// Space: O(n log n).
#include "noya/sparse_table.hpp"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <limits>
#include <utility>
#include <vector>
namespace noya {
/// @brief Sparse-table-based LCA with O(n log n) build and O(1) query.
struct fastlca {
struct minimum_pair_semilattice {
using value_type = std::pair<int, int>;
static value_type unit() {
return {std::numeric_limits<int>::max(), -1};
}
static value_type op(value_type a, value_type b) { return std::min(a, b); }
};
int n;
std::vector<int> dfn;
std::vector<int> d;
std::vector<int64_t> len;
std::vector<int> siz;
sparse_table<minimum_pair_semilattice> ST;
bool wt;
std::vector<int> fa;
std::vector<std::vector<int>> up;
template <class T>
fastlca(const std::vector<T> &g = {}, const bool &wt1 = false,
const int &rt = 0) {
wt = wt1;
if (!g.empty())
build(g, rt);
};
template <class T>
void build(const std::vector<std::vector<T>> &g, const int &rt = 0) {
n = int(g.size());
std::vector<std::vector<int>> g2(n);
for (int u = 0; u < n; u++) {
for (auto &[v, w] : g[u]) {
g2[u].push_back(v);
}
}
build(g2, rt);
len.assign(n, 0);
auto dfs = [&](auto &self, int u) -> void {
for (auto &[v, w] : g[u]) {
if (fa[v] == u) {
len[v] = len[u] + w;
self(self, v);
}
}
};
dfs(dfs, rt);
}
void build(const std::vector<std::vector<int>> &g = {}, const int &rt = 0) {
n = int(g.size());
d.assign(n, 0);
dfn.assign(n, -1);
siz.assign(n, 0);
fa.assign(n, -1);
int idx = 0;
std::vector<std::pair<int, int>> a;
a.reserve(n);
auto dfs = [&](auto &self, int u, int par) -> void {
fa[u] = par;
siz[u] = 1;
dfn[u] = idx++;
a.push_back(par == -1 ? std::pair{-1, -1}
: std::pair{dfn[par], par});
for (int v : g[u]) {
if (v == par) {
continue;
}
d[v] = d[u] + 1;
self(self, v, u);
siz[u] += siz[v];
}
};
dfs(dfs, rt, -1);
ST.build(a);
int dep = 1;
while ((1 << dep) <= std::max(1, n)) {
dep++;
}
up.assign(dep, std::vector<int>(n, -1));
up[0] = fa;
for (int de1 = 1; de1 < dep; de1++) {
for (int u1 = 0; u1 < n; u1++) {
int mid = up[de1 - 1][u1];
if (mid != -1) {
up[de1][u1] = up[de1 - 1][mid];
}
}
}
}
/// @brief Check if node a is in the subtree of node b.
bool is_subtree(int a, int b) {
if (dfn[b] <= dfn[a] && dfn[a] < dfn[b] + siz[b]) {
return true;
} else {
return false;
}
}
/// @brief Return the lowest common ancestor of nodes u and v.
int lca(int u, int v) const {
assert(0 <= u && u < n);
assert(0 <= v && v < n);
if (u == v) {
return u;
} else {
int a = dfn[u];
int b = dfn[v];
if (a > b) {
std::swap(a, b);
}
return ST.prod(a + 1, b + 1).second;
}
}
/// @brief Return the LCA when the tree is re-rooted at c.
int rooted_lca(int a, int b, int c) const {
return lca(a, b) ^ lca(a, c) ^ lca(b, c);
}
/// @brief Return the k-th ancestor of vertex, or -1 when it does not exist.
int kth_ancestor(int u1, int k) const {
assert(0 <= u1 && u1 < n);
if (k < 0 || k > d[u1]) {
return -1;
}
for (int de1 = 0; k > 0; de1++, k >>= 1) {
if (k & 1) {
u1 = up[de1][u1];
}
}
return u1;
}
/// @brief Return the k-th vertex on path first->second, zero-indexed.
int kth_on_path(int lhs, int rhs, int k) const {
int anc = lca(lhs, rhs);
int al = d[lhs] - d[anc];
int bl = d[rhs] - d[anc];
if (k < 0 || k > al + bl) {
return -1;
}
if (k <= al) {
return kth_ancestor(lhs, k);
}
return kth_ancestor(rhs, al + bl - k);
}
/// @brief Return the (weighted or unweighted) distance between nodes a and b.
int64_t distance(int a, int b) const {
int c = lca(a, b);
if (!wt) {
return d[a] + d[b] - d[c] * 2;
} else {
return len[a] + len[b] - len[c] * 2;
}
}
/// @brief Compute the intersection of paths (a,b) and (c,d) as a pair of endpoints.
std::pair<int, int> intersection(int a, int b, int c, int d) const {
int ab = lca(a, b), ac = lca(a, c), ad = lca(a, d);
int bc = lca(b, c), bd = lca(b, d), cd = lca(c, d);
int x = ab ^ ac ^ bc;
int y = ab ^ ad ^ bd;
if (x != y) {
return {x, y};
}
int z = ac ^ ad ^ cd;
if (x != z) {
x = -1;
}
return {x, x};
}
std::pair<int, int> intersection(std::pair<int, int> a,
std::pair<int, int> b) const {
return intersection(a.first, a.second, b.first, b.second);
}
/// @brief Return the list of vertices on the path from a to b.
std::vector<int> path(int a, int b) {
int c = lca(a, b);
std::vector<int> ac;
while (a != c) {
ac.push_back(a);
a = fa[a];
}
std::vector<int> bc;
while (b != c) {
bc.push_back(b);
b = fa[b];
}
std::vector<int> res = std::move(ac);
res.push_back(c);
res.insert(res.end(), bc.rbegin(), bc.rend());
return res;
}
};
} // namespace noya
#ifndef NOYA_LOWEST_COMMON_ANCESTOR_HPP
#define NOYA_LOWEST_COMMON_ANCESTOR_HPP 1
/// @complexity Time: O(n log n) build and O(1) LCA/ancestor queries.
/// Space: O(n log n).
#include "noya/sparse_table.hpp"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <limits>
#include <utility>
#include <vector>
namespace noya {
/// @brief Sparse-table-based LCA with O(n log n) build and O(1) query.
struct fastlca {
struct minimum_pair_semilattice {
using value_type = std::pair<int, int>;
static value_type unit() {
return {std::numeric_limits<int>::max(), -1};
}
static value_type op(value_type a, value_type b) { return std::min(a, b); }
};
int n;
std::vector<int> dfn;
std::vector<int> d;
std::vector<int64_t> len;
std::vector<int> siz;
sparse_table<minimum_pair_semilattice> ST;
bool wt;
std::vector<int> fa;
std::vector<std::vector<int>> up;
template <class T>
fastlca(const std::vector<T> &g = {}, const bool &wt1 = false,
const int &rt = 0) {
wt = wt1;
if (!g.empty())
build(g, rt);
};
template <class T>
void build(const std::vector<std::vector<T>> &g, const int &rt = 0) {
n = int(g.size());
std::vector<std::vector<int>> g2(n);
for (int u = 0; u < n; u++) {
for (auto &[v, w] : g[u]) {
g2[u].push_back(v);
}
}
build(g2, rt);
len.assign(n, 0);
auto dfs = [&](auto &self, int u) -> void {
for (auto &[v, w] : g[u]) {
if (fa[v] == u) {
len[v] = len[u] + w;
self(self, v);
}
}
};
dfs(dfs, rt);
}
void build(const std::vector<std::vector<int>> &g = {}, const int &rt = 0) {
n = int(g.size());
d.assign(n, 0);
dfn.assign(n, -1);
siz.assign(n, 0);
fa.assign(n, -1);
int idx = 0;
std::vector<std::pair<int, int>> a;
a.reserve(n);
auto dfs = [&](auto &self, int u, int par) -> void {
fa[u] = par;
siz[u] = 1;
dfn[u] = idx++;
a.push_back(par == -1 ? std::pair{-1, -1}
: std::pair{dfn[par], par});
for (int v : g[u]) {
if (v == par) {
continue;
}
d[v] = d[u] + 1;
self(self, v, u);
siz[u] += siz[v];
}
};
dfs(dfs, rt, -1);
ST.build(a);
int dep = 1;
while ((1 << dep) <= std::max(1, n)) {
dep++;
}
up.assign(dep, std::vector<int>(n, -1));
up[0] = fa;
for (int de1 = 1; de1 < dep; de1++) {
for (int u1 = 0; u1 < n; u1++) {
int mid = up[de1 - 1][u1];
if (mid != -1) {
up[de1][u1] = up[de1 - 1][mid];
}
}
}
}
/// @brief Check if node a is in the subtree of node b.
bool is_subtree(int a, int b) {
if (dfn[b] <= dfn[a] && dfn[a] < dfn[b] + siz[b]) {
return true;
} else {
return false;
}
}
/// @brief Return the lowest common ancestor of nodes u and v.
int lca(int u, int v) const {
assert(0 <= u && u < n);
assert(0 <= v && v < n);
if (u == v) {
return u;
} else {
int a = dfn[u];
int b = dfn[v];
if (a > b) {
std::swap(a, b);
}
return ST.prod(a + 1, b + 1).second;
}
}
/// @brief Return the LCA when the tree is re-rooted at c.
int rooted_lca(int a, int b, int c) const {
return lca(a, b) ^ lca(a, c) ^ lca(b, c);
}
/// @brief Return the k-th ancestor of vertex, or -1 when it does not exist.
int kth_ancestor(int u1, int k) const {
assert(0 <= u1 && u1 < n);
if (k < 0 || k > d[u1]) {
return -1;
}
for (int de1 = 0; k > 0; de1++, k >>= 1) {
if (k & 1) {
u1 = up[de1][u1];
}
}
return u1;
}
/// @brief Return the k-th vertex on path first->second, zero-indexed.
int kth_on_path(int lhs, int rhs, int k) const {
int anc = lca(lhs, rhs);
int al = d[lhs] - d[anc];
int bl = d[rhs] - d[anc];
if (k < 0 || k > al + bl) {
return -1;
}
if (k <= al) {
return kth_ancestor(lhs, k);
}
return kth_ancestor(rhs, al + bl - k);
}
/// @brief Return the (weighted or unweighted) distance between nodes a and b.
int64_t distance(int a, int b) const {
int c = lca(a, b);
if (!wt) {
return d[a] + d[b] - d[c] * 2;
} else {
return len[a] + len[b] - len[c] * 2;
}
}
/// @brief Compute the intersection of paths (a,b) and (c,d) as a pair of endpoints.
std::pair<int, int> intersection(int a, int b, int c, int d) const {
int ab = lca(a, b), ac = lca(a, c), ad = lca(a, d);
int bc = lca(b, c), bd = lca(b, d), cd = lca(c, d);
int x = ab ^ ac ^ bc;
int y = ab ^ ad ^ bd;
if (x != y) {
return {x, y};
}
int z = ac ^ ad ^ cd;
if (x != z) {
x = -1;
}
return {x, x};
}
std::pair<int, int> intersection(std::pair<int, int> a,
std::pair<int, int> b) const {
return intersection(a.first, a.second, b.first, b.second);
}
/// @brief Return the list of vertices on the path from a to b.
std::vector<int> path(int a, int b) {
int c = lca(a, b);
std::vector<int> ac;
while (a != c) {
ac.push_back(a);
a = fa[a];
}
std::vector<int> bc;
while (b != c) {
bc.push_back(b);
b = fa[b];
}
std::vector<int> res = std::move(ac);
res.push_back(c);
res.insert(res.end(), bc.rbegin(), bc.rend());
return res;
}
};
} // namespace noya
#endif // NOYA_LOWEST_COMMON_ANCESTOR_HPP
#include <algorithm>
#include <bit>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <type_traits>
#include <utility>
#include <vector>
/// @complexity Time: O(n log n) build and O(1) LCA/ancestor queries.
/// Space: O(n log n).
/// @complexity Time: O(n log n) build and O(1) idempotent range query.
/// Space: O(n log n).
namespace noya {
namespace internal {
template <class Algebra, auto fn, auto e,
bool old = !std::is_same_v<decltype(fn), std::nullptr_t>>
struct sparse_table_algebra;
template <class Semilattice, auto fn, auto e>
struct sparse_table_algebra<Semilattice, fn, e, false> {
static_assert(std::is_same_v<decltype(e), std::nullptr_t>,
"a policy sparse_table gets its identity from unit()");
using value_type = typename Semilattice::value_type;
static value_type unit() { return Semilattice::unit(); }
static value_type op(const value_type &l, const value_type &r) {
return Semilattice::op(l, r);
}
};
template <class Value, auto fn, auto e>
struct sparse_table_algebra<Value, fn, e, true> {
using value_type = Value;
static value_type unit() {
if constexpr (std::is_same_v<decltype(e), std::nullptr_t>) {
return value_type{};
} else {
return value_type(e);
}
}
static value_type op(const value_type &l, const value_type &r) {
return fn(l, r);
}
};
} // namespace internal
/// @brief Static O(1) range product for an idempotent semilattice.
/// The preferred interface is sparse_table<Semilattice>, where Semilattice
/// provides value_type, unit(), and an associative, idempotent op(). The legacy
/// sparse_table<Value, operation, identity> spelling remains supported.
/// @details For k = floor(log2(r-l)), [l, r) is covered by the length-2^k
/// blocks beginning at l and ending at r. They may overlap, so combining them
/// is correct precisely because op(x, x) = x.
template <class Algebra, auto fn = nullptr, auto e = nullptr>
class sparse_table {
using algebra_type = internal::sparse_table_algebra<Algebra, fn, e>;
public:
using value_type = typename algebra_type::value_type;
sparse_table() = default;
explicit sparse_table(const std::vector<value_type> &a) { build(a); }
/// @brief Rebuild from a static array.
void build(const std::vector<value_type> &a) {
n = int(a.size());
int lg = int(std::bit_width(static_cast<unsigned>(n)));
st.assign(lg, {});
if (n == 0) {
return;
}
st[0] = a;
for (int dep = 1; dep < lg; dep++) {
int w = 1 << dep;
int hf = w >> 1;
st[dep].resize(n - w + 1);
for (int l = 0; l + w <= n; l++) {
st[dep][l] = algebra_type::op(st[dep - 1][l], st[dep - 1][l + hf]);
}
}
}
int size() const { return n; }
bool empty() const { return n == 0; }
/// @brief Return the idempotent product over [l, r).
value_type prod(int l, int r) const {
assert(0 <= l && l <= r && r <= n);
if (l == r) {
return algebra_type::unit();
}
int dep = int(std::bit_width(static_cast<unsigned>(r - l))) - 1;
int w = 1 << dep;
return algebra_type::op(st[dep][l], st[dep][r - w]);
}
private:
int n = 0;
std::vector<std::vector<value_type>> st;
};
} // namespace noya
namespace noya {
/// @brief Sparse-table-based LCA with O(n log n) build and O(1) query.
struct fastlca {
struct minimum_pair_semilattice {
using value_type = std::pair<int, int>;
static value_type unit() {
return {std::numeric_limits<int>::max(), -1};
}
static value_type op(value_type a, value_type b) { return std::min(a, b); }
};
int n;
std::vector<int> dfn;
std::vector<int> d;
std::vector<int64_t> len;
std::vector<int> siz;
sparse_table<minimum_pair_semilattice> ST;
bool wt;
std::vector<int> fa;
std::vector<std::vector<int>> up;
template <class T>
fastlca(const std::vector<T> &g = {}, const bool &wt1 = false,
const int &rt = 0) {
wt = wt1;
if (!g.empty())
build(g, rt);
};
template <class T>
void build(const std::vector<std::vector<T>> &g, const int &rt = 0) {
n = int(g.size());
std::vector<std::vector<int>> g2(n);
for (int u = 0; u < n; u++) {
for (auto &[v, w] : g[u]) {
g2[u].push_back(v);
}
}
build(g2, rt);
len.assign(n, 0);
auto dfs = [&](auto &self, int u) -> void {
for (auto &[v, w] : g[u]) {
if (fa[v] == u) {
len[v] = len[u] + w;
self(self, v);
}
}
};
dfs(dfs, rt);
}
void build(const std::vector<std::vector<int>> &g = {}, const int &rt = 0) {
n = int(g.size());
d.assign(n, 0);
dfn.assign(n, -1);
siz.assign(n, 0);
fa.assign(n, -1);
int idx = 0;
std::vector<std::pair<int, int>> a;
a.reserve(n);
auto dfs = [&](auto &self, int u, int par) -> void {
fa[u] = par;
siz[u] = 1;
dfn[u] = idx++;
a.push_back(par == -1 ? std::pair{-1, -1}
: std::pair{dfn[par], par});
for (int v : g[u]) {
if (v == par) {
continue;
}
d[v] = d[u] + 1;
self(self, v, u);
siz[u] += siz[v];
}
};
dfs(dfs, rt, -1);
ST.build(a);
int dep = 1;
while ((1 << dep) <= std::max(1, n)) {
dep++;
}
up.assign(dep, std::vector<int>(n, -1));
up[0] = fa;
for (int de1 = 1; de1 < dep; de1++) {
for (int u1 = 0; u1 < n; u1++) {
int mid = up[de1 - 1][u1];
if (mid != -1) {
up[de1][u1] = up[de1 - 1][mid];
}
}
}
}
/// @brief Check if node a is in the subtree of node b.
bool is_subtree(int a, int b) {
if (dfn[b] <= dfn[a] && dfn[a] < dfn[b] + siz[b]) {
return true;
} else {
return false;
}
}
/// @brief Return the lowest common ancestor of nodes u and v.
int lca(int u, int v) const {
assert(0 <= u && u < n);
assert(0 <= v && v < n);
if (u == v) {
return u;
} else {
int a = dfn[u];
int b = dfn[v];
if (a > b) {
std::swap(a, b);
}
return ST.prod(a + 1, b + 1).second;
}
}
/// @brief Return the LCA when the tree is re-rooted at c.
int rooted_lca(int a, int b, int c) const {
return lca(a, b) ^ lca(a, c) ^ lca(b, c);
}
/// @brief Return the k-th ancestor of vertex, or -1 when it does not exist.
int kth_ancestor(int u1, int k) const {
assert(0 <= u1 && u1 < n);
if (k < 0 || k > d[u1]) {
return -1;
}
for (int de1 = 0; k > 0; de1++, k >>= 1) {
if (k & 1) {
u1 = up[de1][u1];
}
}
return u1;
}
/// @brief Return the k-th vertex on path first->second, zero-indexed.
int kth_on_path(int lhs, int rhs, int k) const {
int anc = lca(lhs, rhs);
int al = d[lhs] - d[anc];
int bl = d[rhs] - d[anc];
if (k < 0 || k > al + bl) {
return -1;
}
if (k <= al) {
return kth_ancestor(lhs, k);
}
return kth_ancestor(rhs, al + bl - k);
}
/// @brief Return the (weighted or unweighted) distance between nodes a and b.
int64_t distance(int a, int b) const {
int c = lca(a, b);
if (!wt) {
return d[a] + d[b] - d[c] * 2;
} else {
return len[a] + len[b] - len[c] * 2;
}
}
/// @brief Compute the intersection of paths (a,b) and (c,d) as a pair of endpoints.
std::pair<int, int> intersection(int a, int b, int c, int d) const {
int ab = lca(a, b), ac = lca(a, c), ad = lca(a, d);
int bc = lca(b, c), bd = lca(b, d), cd = lca(c, d);
int x = ab ^ ac ^ bc;
int y = ab ^ ad ^ bd;
if (x != y) {
return {x, y};
}
int z = ac ^ ad ^ cd;
if (x != z) {
x = -1;
}
return {x, x};
}
std::pair<int, int> intersection(std::pair<int, int> a,
std::pair<int, int> b) const {
return intersection(a.first, a.second, b.first, b.second);
}
/// @brief Return the list of vertices on the path from a to b.
std::vector<int> path(int a, int b) {
int c = lca(a, b);
std::vector<int> ac;
while (a != c) {
ac.push_back(a);
a = fa[a];
}
std::vector<int> bc;
while (b != c) {
bc.push_back(b);
b = fa[b];
}
std::vector<int> res = std::move(ac);
res.push_back(c);
res.insert(res.end(), bc.rbegin(), bc.rend());
return res;
}
};
} // namespace noya