lib/tree/linear_lca.hpp

• View this file on GitHub
• Last update: 2025-07-09 13:18:43+09:00
• Include: #include "lib/tree/linear_lca.hpp"

Depends on

• 線形 Sparse Table (lib/data_structure/linear_sparse_table.hpp)
• スパーステーブル (lib/data_structure/sparse_table.hpp)
• 重み付きグラフ (lib/graph/graph.hpp)
• lib/internal/internal_csr.hpp

Required by

• lib/tree/auxiliary_tree.hpp

Verified with

• test/aoj/challenge/2270.test.cpp
• test/yosupo/tree/lowest_common_ancestor.2.test.cpp
• test/yukicoder/0901.test.cpp

Code

#pragma once
#include <algorithm>
#include <limits>
#include <stack>
#include <utility>
#include <vector>
#include "data_structure/linear_sparse_table.hpp"
#include "graph/graph.hpp"
#include "internal/internal_csr.hpp"

struct linear_lca {
  private:
    struct S {
        int depth, index;

        constexpr bool operator<(const S &rhs) const { return depth < rhs.depth; }
        constexpr bool operator==(const S &rhs) const = default;
    };

    struct M {
        using value_type = S;
        static constexpr S id() { return S{std::numeric_limits<int>::max(), -1}; }
        static constexpr S op(const S &lhs, const S &rhs) { return std::min(lhs, rhs); }
    };

  public:
    template <class T>
    linear_lca(const Graph<T> &g, int r = 0) : ord(g.size(), -1), lst() {
        std::vector<S> v;
        std::stack<std::pair<int, int>> st;
        st.emplace(r, 0);
        while (!st.empty()) {
            auto [x, d] = st.top();
            st.pop();
            if (x < 0) {
                v.emplace_back(d, ~x);
                continue;
            }
            ord[x] = v.size();
            v.emplace_back(d, x);
            for (auto e : g[x]) {
                if (ord[e.to()] != -1) continue;
                st.emplace(~x, d);
                st.emplace(e.to(), d + 1);
            }
        }
        lst = linear_sparse_table<M>(v);
    }
    linear_lca(const internal::graph_csr &g, int r = 0) : ord(g.size(), -1), lst() {
        std::vector<S> v;
        std::stack<std::pair<int, int>> st;
        st.emplace(r, 0);
        while (!st.empty()) {
            auto [x, d] = st.top();
            st.pop();
            if (x < 0) {
                v.emplace_back(d, ~x);
                continue;
            }
            ord[x] = v.size();
            v.emplace_back(d, x);
            for (int y : g[x]) {
                if (ord[y] != -1) continue;
                st.emplace(~x, d);
                st.emplace(y, d + 1);
            }
        }
        lst = linear_sparse_table<M>(v);
    }

    int operator()(int u, int v) const { return lca(u, v); }

    int lca(int u, int v) const {
        auto [l, r] = std::minmax(ord[u], ord[v]);
        return lst.prod(l, r + 1).index;
    }

  private:
    std::vector<int> ord;
    linear_sparse_table<M> lst;
};

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/resolver.py", line 291, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 242, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 479, in update
    self._resolve(pathlib.Path(included), included_from=path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 286, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: data_structure/linear_sparse_table.hpp: line -1: no such header

Back to top page