最深共通祖先 (squaring) (Graph/lowest_common_ancestor_squaring.cpp)
- category: Graph
-
View this file on GitHub
- Last commit date: 2020-07-11 14:53:01+09:00
Depends on
Verified with
Code
#ifndef H_lowest_common_ancestor_squaring
#define H_lowest_common_ancestor_squaring
/**
* @brief 最深共通祖先 (squaring)
* @author えびちゃん
*/
#include <cstddef>
#include <algorithm>
#include <tuple>
#include <utility>
#include <vector>
#include "utility/literals.cpp"
class lowest_common_ancestor {
public:
using size_type = size_t;
private:
std::vector<size_type> M_d;
std::vector<std::vector<size_type>> M_p;
template <typename Tree>
void M_dfs(Tree const& g, size_type v, size_type p) {
for (auto const& e: g[v]) {
size_type u = e.target();
if (u == p) continue;
M_p[0][u] = v;
M_d[u] = M_d[v] + 1;
M_dfs(g, u, v);
}
}
void M_double() {
size_type n = M_p[0].size();
while (true) {
bool valid = false;
auto const& back = M_p.back();
std::vector<size_type> tmp(n, -1);
for (size_type i = 0; i < n; ++i) {
if (back[i] == -1_zu) continue;
tmp[i] = back[back[i]];
if (tmp[i] != -1_zu) valid = true;
}
if (!valid) break;
M_p.push_back(std::move(tmp));
}
}
public:
lowest_common_ancestor() = default;
lowest_common_ancestor(lowest_common_ancestor const&) = default;
lowest_common_ancestor(lowest_common_ancestor&&) = default;
template <typename Tree>
lowest_common_ancestor(Tree const& g, size_type r) {
size_type n = g.size();
M_d.assign(n, 0);
M_p.emplace_back(n, -1);
M_dfs(g, r, -1);
M_double();
}
lowest_common_ancestor& operator =(lowest_common_ancestor const&) = default;
lowest_common_ancestor& operator =(lowest_common_ancestor&&) = default;
size_type operator ()(size_type u, size_type v) const {
if (M_d[u] > M_d[v]) std::swap(u, v);
if (M_d[u] < M_d[v]) {
size_type d = M_d[v] - M_d[u];
for (size_type i = 0; i < M_p.size(); ++i)
if (d >> i & 1) v = M_p[i][v];
}
if (u == v) return u;
for (size_type i = M_p.size(); i--;) {
if (M_p[i][u] == M_p[i][v]) continue;
u = M_p[i][u];
v = M_p[i][v];
}
return M_p[0][u];
}
};
#endif /* !defined(H_lowest_common_ancestor_squaring) */
#line 1 "Graph/lowest_common_ancestor_squaring.cpp"
/**
* @brief 最深共通祖先 (squaring)
* @author えびちゃん
*/
#include <cstddef>
#include <algorithm>
#include <tuple>
#include <utility>
#include <vector>
#line 1 "utility/literals.cpp"
/**
* @brief ユーザ定義リテラル
* @author えびちゃん
*/
#line 10 "utility/literals.cpp"
#include <cstdint>
constexpr intmax_t operator ""_jd(unsigned long long n) { return n; }
constexpr uintmax_t operator ""_ju(unsigned long long n) { return n; }
constexpr size_t operator ""_zu(unsigned long long n) { return n; }
constexpr ptrdiff_t operator ""_td(unsigned long long n) { return n; }
constexpr int8_t operator ""_i8(unsigned long long n) { return n; }
constexpr int16_t operator ""_i16(unsigned long long n) { return n; }
constexpr int32_t operator ""_i32(unsigned long long n) { return n; }
constexpr int64_t operator ""_i64(unsigned long long n) { return n; }
constexpr uint8_t operator ""_u8(unsigned long long n) { return n; }
constexpr uint16_t operator ""_u16(unsigned long long n) { return n; }
constexpr uint32_t operator ""_u32(unsigned long long n) { return n; }
constexpr uint64_t operator ""_u64(unsigned long long n) { return n; }
#line 16 "Graph/lowest_common_ancestor_squaring.cpp"
class lowest_common_ancestor {
public:
using size_type = size_t;
private:
std::vector<size_type> M_d;
std::vector<std::vector<size_type>> M_p;
template <typename Tree>
void M_dfs(Tree const& g, size_type v, size_type p) {
for (auto const& e: g[v]) {
size_type u = e.target();
if (u == p) continue;
M_p[0][u] = v;
M_d[u] = M_d[v] + 1;
M_dfs(g, u, v);
}
}
void M_double() {
size_type n = M_p[0].size();
while (true) {
bool valid = false;
auto const& back = M_p.back();
std::vector<size_type> tmp(n, -1);
for (size_type i = 0; i < n; ++i) {
if (back[i] == -1_zu) continue;
tmp[i] = back[back[i]];
if (tmp[i] != -1_zu) valid = true;
}
if (!valid) break;
M_p.push_back(std::move(tmp));
}
}
public:
lowest_common_ancestor() = default;
lowest_common_ancestor(lowest_common_ancestor const&) = default;
lowest_common_ancestor(lowest_common_ancestor&&) = default;
template <typename Tree>
lowest_common_ancestor(Tree const& g, size_type r) {
size_type n = g.size();
M_d.assign(n, 0);
M_p.emplace_back(n, -1);
M_dfs(g, r, -1);
M_double();
}
lowest_common_ancestor& operator =(lowest_common_ancestor const&) = default;
lowest_common_ancestor& operator =(lowest_common_ancestor&&) = default;
size_type operator ()(size_type u, size_type v) const {
if (M_d[u] > M_d[v]) std::swap(u, v);
if (M_d[u] < M_d[v]) {
size_type d = M_d[v] - M_d[u];
for (size_type i = 0; i < M_p.size(); ++i)
if (d >> i & 1) v = M_p[i][v];
}
if (u == v) return u;
for (size_type i = M_p.size(); i--;) {
if (M_p[i][u] == M_p[i][v]) continue;
u = M_p[i][u];
v = M_p[i][v];
}
return M_p[0][u];
}
};