Lowest Common Ancestor
(Src/Graph/Tree/LowestCommonAncestor.hpp)

View this file on GitHub
Last update: 2024-12-07 19:29:25+09:00
Include: #include "Src/Graph/Tree/LowestCommonAncestor.hpp"

概要

関数オブジェクトの様になっています。 operator()(usize u, usize v)でuとvのLCAが求まります。

ライブラリの使い方

コンストラクタで Tree と根の頂点番号を与えること。頂点番号を指定しなかった場合は頂点 $0$ を根として構築する。

Depends on

Required by

Auxiliary Tree (指定された頂点たちの最小共通祖先関係を保って木を圧縮してできる補助的な木) (Src/Graph/Tree/AuxiliaryTree.hpp)

Verified with

Code

#pragma once

#include "../../Template/TypeAlias.hpp"
#include "../../Algebra/Monoid/ChminMonoid.hpp"
#include "../../DataStructure/SparseTable/SparseTable.hpp"

#include <cassert>
#include <vector>

namespace zawa {

template <class V>
class LowestCommonAncestor {
private:
    using Monoid = ChminMonoid<u32, V>;

public:
    LowestCommonAncestor() = default;

    LowestCommonAncestor(const std::vector<std::vector<V>>& tree, V r = V{}) 
        : n_{tree.size()}, depth_(tree.size()), L_(tree.size()), R_(tree.size()), st_{} {
            std::vector<typename Monoid::Element> init;
            init.reserve(2 * size());
            auto dfs{[&](auto dfs, V v, V p) -> void {
                depth_[v] = (p == INVALID ? 0u : depth_[p] + 1);
                L_[v] = (u32)init.size();
                for (auto x : tree[v]) {
                    if (x == p) {
                        continue;
                    }
                    init.emplace_back(depth_[v], v);
                    dfs(dfs, x, v);
                }
                R_[v] = (u32)init.size();
            }};
            dfs(dfs, r, INVALID);
            st_ = SparseTable<Monoid>(init);
    }

    V operator()(V u, V v) const {
        assert(verify(u));
        assert(verify(v));
        if (L_[u] > L_[v]) {
            std::swap(u, v);
        }
        return u == v ? u : st_.product(L_[u], R_[v]).value();
    }

    V lca(V u, V v) const {
        return (*this)(u, v);
    }

    inline u32 depth(V v) const noexcept {
        assert(verify(v));
        return depth_[v];
    }

    u32 distance(V u, V v) const {
        assert(verify(u));
        assert(verify(v));
        return depth(u) + depth(v) - 2u * depth((*this)(u, v));
    }

    bool isAncestor(V p, V v) const {
        assert(verify(p));
        assert(verify(v));
        return L_[p] <= L_[v] and R_[v] <= R_[p];
    }

protected:
    u32 left(V v) const noexcept {
        return L_[v];
    }

    inline usize size() const {
        return n_;
    }

    inline bool verify(V v) const {
        return v < (V)size();
    }

private:
    static constexpr V INVALID{static_cast<V>(-1)};
    usize n_{};
    std::vector<u32> depth_, L_, R_;
    SparseTable<Monoid> st_;
};

} // namespace zawa

#line 2 "Src/Graph/Tree/LowestCommonAncestor.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 2 "Src/Algebra/Monoid/ChminMonoid.hpp"

#line 4 "Src/Algebra/Monoid/ChminMonoid.hpp"

#include <algorithm>
#include <optional>

namespace zawa {

template <class T, class U>
class ChminMonoidData {
private:
    std::optional<T> priority_{};
    U value_{};
public:
    ChminMonoidData() = default;
    ChminMonoidData(const U& value)
        : priority_{std::nullopt}, value_{value} {}
    ChminMonoidData(const T& priority, const U& value)
        : priority_{priority}, value_{value} {}

    constexpr bool infty() const noexcept {
        return !priority_.has_value();
    }
    constexpr const T& priority() const noexcept {
        return priority_.value();
    }
    constexpr const U& value() const noexcept {
        return value_;
    }
    friend constexpr bool operator<(const ChminMonoidData& l, const ChminMonoidData& r) {
        if (l.infty()) return false;
        else if (r.infty()) return true;
        else return l.priority() < r.priority();
    }
};

template <class T, class U>
struct ChminMonoid {
    using Element = ChminMonoidData<T, U>;
    static Element identity() noexcept {
        return Element{};
    }
    // タイブレークはl側を優先するようになっている。
    static Element operation(const Element& l, const Element& r) noexcept {
        return (r < l ? r : l);
    }
};

} // namespace zawa
#line 2 "Src/DataStructure/SparseTable/SparseTable.hpp"

#line 4 "Src/DataStructure/SparseTable/SparseTable.hpp"

#include <vector>
#include <cassert>
#include <ostream>

namespace zawa {

template <class Structure>
class SparseTable {
private:
    using Value = typename Structure::Element;
    std::vector<u32> L;
    std::vector<std::vector<Value>> dat;
public:

    SparseTable() : L{}, dat{} {}
    SparseTable(const std::vector<Value>& a) : L(a.size() + 1), dat{} {
        for (u32 i{1} ; i < L.size() ; i++) {
            L[i] = L[i - 1] + (i >> (L[i - 1] + 1));
        }
        dat.resize(L.back() + 1);
        dat[0] = a;
        for (u32 i{1}, len{2} ; i < dat.size() ; i++, len <<= 1) {
            dat[i] = dat[i - 1];
            for (u32 j{} ; j + len - 1 < dat[i].size() ; j++) {
                dat[i][j] = Structure::operation(dat[i - 1][j], dat[i - 1][j + (len >> 1)]);
            }
        }
    }

    Value product(u32 l, u32 r) const {
        assert(l <= r);
        assert(l < dat[0].size());
        assert(r <= dat[0].size());
        u32 now{L[r - l]};
        return Structure::operation(dat[now][l], dat[now][r - (1 << now)]);
    }

    friend std::ostream& operator<<(std::ostream& os, const SparseTable<Structure>& spt) {
        for (u32 i{}, len{1} ; i < spt.dat.size() ; i++, len <<= 1) {
            os << "length = " << len << '\n';
            for (u32 j{} ; j + len - 1 < spt.dat[i].size() ; j++) {
                os << spt.dat[i][j] << (j + len == spt.dat[i].size() ? '\n' : ' ');
            }
        }
        return os;
    }
};

} // namespace zawa
#line 6 "Src/Graph/Tree/LowestCommonAncestor.hpp"

#line 9 "Src/Graph/Tree/LowestCommonAncestor.hpp"

namespace zawa {

template <class V>
class LowestCommonAncestor {
private:
    using Monoid = ChminMonoid<u32, V>;

public:
    LowestCommonAncestor() = default;

    LowestCommonAncestor(const std::vector<std::vector<V>>& tree, V r = V{}) 
        : n_{tree.size()}, depth_(tree.size()), L_(tree.size()), R_(tree.size()), st_{} {
            std::vector<typename Monoid::Element> init;
            init.reserve(2 * size());
            auto dfs{[&](auto dfs, V v, V p) -> void {
                depth_[v] = (p == INVALID ? 0u : depth_[p] + 1);
                L_[v] = (u32)init.size();
                for (auto x : tree[v]) {
                    if (x == p) {
                        continue;
                    }
                    init.emplace_back(depth_[v], v);
                    dfs(dfs, x, v);
                }
                R_[v] = (u32)init.size();
            }};
            dfs(dfs, r, INVALID);
            st_ = SparseTable<Monoid>(init);
    }

    V operator()(V u, V v) const {
        assert(verify(u));
        assert(verify(v));
        if (L_[u] > L_[v]) {
            std::swap(u, v);
        }
        return u == v ? u : st_.product(L_[u], R_[v]).value();
    }

    V lca(V u, V v) const {
        return (*this)(u, v);
    }

    inline u32 depth(V v) const noexcept {
        assert(verify(v));
        return depth_[v];
    }

    u32 distance(V u, V v) const {
        assert(verify(u));
        assert(verify(v));
        return depth(u) + depth(v) - 2u * depth((*this)(u, v));
    }

    bool isAncestor(V p, V v) const {
        assert(verify(p));
        assert(verify(v));
        return L_[p] <= L_[v] and R_[v] <= R_[p];
    }

protected:
    u32 left(V v) const noexcept {
        return L_[v];
    }

    inline usize size() const {
        return n_;
    }

    inline bool verify(V v) const {
        return v < (V)size();
    }

private:
    static constexpr V INVALID{static_cast<V>(-1)};
    usize n_{};
    std::vector<u32> depth_, L_, R_;
    SparseTable<Monoid> st_;
};

} // namespace zawa

Lowest Common Ancestor (Src/Graph/Tree/LowestCommonAncestor.hpp)

概要

ライブラリの使い方

Depends on

Required by

Verified with

Code

Lowest Common Ancestor
(Src/Graph/Tree/LowestCommonAncestor.hpp)