This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub dgcnz/cp-library
#include "cplib/graph/lca.hpp"
#ifndef CPLIB_LCA_HPP #define CPLIB_LCA_HPP #include "cplib/graph/graph.hpp" #include <cmath> #include <functional> #include <vector> namespace cplib { using namespace std; template <typename W> struct LCA { Graph<W> const & g; vector<vector<int>> up; vector<int> tin, tout; LCA(Graph<W> const &g) : g(g), up(g.size(), vector<int>(log2(g.size()) + 2)), tin(g.size()), tout(g.size()) { int timer = 0, n = g.size(); function<void(int, int)> dfs = [&](int u, int p) { tin[u] = ++timer; up[u][0] = p; for (int i = 1, height = up[0].size(); i < height; ++i) up[u][i] = up[up[u][i - 1]][i - 1]; for (auto vw : g[u]) if (g.vertex(vw) != p) dfs(g.vertex(vw), u); tout[u] = ++timer; }; for (int u = 0; u < n; ++u) if (tin[u] == 0) dfs(u, u); } bool is_ancestor(int u, int v) const { return tin[u] <= tin[v] and tout[u] >= tout[v]; } int ancestor(int u, int k) const { int i; while (k) { i = 8 * sizeof(k) - __builtin_clz(k) - 1; u = up[u][i]; k ^= 1LL << i; } if (up[u][0] == u) return -1; return u; } int lca(int u, int v) const { if (is_ancestor(u, v)) return u; if (is_ancestor(v, u)) return v; for (int i = up[0].size() - 1; i >= 0; --i) if (!is_ancestor(up[u][i], v)) u = up[u][i]; return up[u][0]; } int operator()(int u, int v) const { return lca(u, v); } }; } // namespace cplib #endif // CPLIB_LCA_HPP
#line 1 "cplib/graph/lca.hpp" #line 1 "cplib/graph/graph.hpp" #include <algorithm> #include <cassert> #include <utility> #include <vector> namespace cplib { using namespace std; template <typename W> struct Graph { using adj_list = vector<pair<int, W>>; vector<adj_list> g; Graph(int n = 0) : g(n) {} size_t size() const { return g.size(); } int vertex(pair<int, W> e) const { return e.first; } void add_edge(int u, int v) { g[u].emplace_back(v, W()); } void add_edge(int u, int v, W weights) { g[u].emplace_back(v, weights); } void add_undirected_edge(int u, int v) { g[u].emplace_back(v, W()); g[v].emplace_back(u, W()); } void add_undirected_edge(int u, int v, W weights) { g[u].emplace_back(v, weights); g[v].emplace_back(u, weights); } int add_node(void) { g.push_back({}); return g.size() - 1; } adj_list &operator[](int u) { return g[u]; } adj_list operator[](int u) const { return g[u]; } typename vector<adj_list>::iterator begin() { return g.begin(); }; typename vector<adj_list>::iterator end() { return g.end(); } typename vector<adj_list>::const_iterator begin() const { return g.begin(); }; typename vector<adj_list>::const_iterator end() const { return g.end(); } }; template <> struct Graph<void> { using adj_list = vector<int>; vector<adj_list> g; Graph(int n = 0) : g(n) {} size_t size() const { return g.size(); } int vertex(int e) const { return e; } void add_edge(int u, int v) { g[u].emplace_back(v); } void add_undirected_edge(int u, int v) { g[u].push_back(v); g[v].push_back(u); } int add_node(void) { g.push_back({}); return g.size() - 1; } adj_list &operator[](int u) { return g[u]; } adj_list operator[](int u) const { return g[u]; } typename vector<adj_list>::iterator begin() { return g.begin(); }; typename vector<adj_list>::iterator end() { return g.end(); } typename vector<adj_list>::const_iterator begin() const { return g.begin(); }; typename vector<adj_list>::const_iterator end() const { return g.end(); } }; using UndirectedGraph = Graph<void>; } // namespace cplib #line 5 "cplib/graph/lca.hpp" #include <cmath> #include <functional> #line 8 "cplib/graph/lca.hpp" namespace cplib { using namespace std; template <typename W> struct LCA { Graph<W> const & g; vector<vector<int>> up; vector<int> tin, tout; LCA(Graph<W> const &g) : g(g), up(g.size(), vector<int>(log2(g.size()) + 2)), tin(g.size()), tout(g.size()) { int timer = 0, n = g.size(); function<void(int, int)> dfs = [&](int u, int p) { tin[u] = ++timer; up[u][0] = p; for (int i = 1, height = up[0].size(); i < height; ++i) up[u][i] = up[up[u][i - 1]][i - 1]; for (auto vw : g[u]) if (g.vertex(vw) != p) dfs(g.vertex(vw), u); tout[u] = ++timer; }; for (int u = 0; u < n; ++u) if (tin[u] == 0) dfs(u, u); } bool is_ancestor(int u, int v) const { return tin[u] <= tin[v] and tout[u] >= tout[v]; } int ancestor(int u, int k) const { int i; while (k) { i = 8 * sizeof(k) - __builtin_clz(k) - 1; u = up[u][i]; k ^= 1LL << i; } if (up[u][0] == u) return -1; return u; } int lca(int u, int v) const { if (is_ancestor(u, v)) return u; if (is_ancestor(v, u)) return v; for (int i = up[0].size() - 1; i >= 0; --i) if (!is_ancestor(up[u][i], v)) u = up[u][i]; return up[u][0]; } int operator()(int u, int v) const { return lca(u, v); } }; } // namespace cplib