オフライン Level Ancestor (Offline Level Ancestor)
(src/graph/tree/offline-query/offline-query-level-ancestor.hpp)

• View this file on GitHub
• Last update: 2023-07-30 00:54:52+09:00
• Include: #include "src/graph/tree/offline-query/offline-query-level-ancestor.hpp"

Appendix

テンプレートパラメータに渡すグラフ $G$ の仕様について

コンストラクタ

OfflineLAQuery(const G &g)

Level ancestor を求める木 g を渡す。

add_query

void add_query(usize v, usize level)

頂点 $v$ の祖先であって深さが $level$ であるような頂点 $la(v, level)$ を求めるクエリを追加する。

後述する build をした後、la(v, level) によって $la(v, level)$ を得ることができる。

制約

• $0 \leq v < |V|$

計算量

• $O(1)$

build

void build(usize root)

頂点 root を根とする根付き木上での Level ancestor を計算する。

制約

• $0 \leq root < |V|$

計算量

• $O(|V| + Q)$
  • 追加されたクエリの数を $Q$ とする

la

std::optional< usize > la(usize v, usize level)

$la(v, level)$ を std::optional でラップして返す。根は直近で呼ばれた build(root) に依存する。

頂点 $v$ の祖先であって深さが $level$ であるような頂点が存在しないとき std::nullopt が返る。

la() の使用例

$la(v, level)$ が存在するときは $la(v, level)$ となる頂点の番号を、そうでない場合 -1 を出力するサンプル

OfflineLAQuery la_query(g);

...

auto la = la_query.la(v, level);

if (la) {
  std::cout << la.value() << std::endl;
} else {
  std::cout << -1 << std::endl;
}

制約

• add_query(v, level) が呼ばれており、かつその後に build(root) が呼ばれていること。

計算量

• $O(1)$

Depends on

• rep 構造体 (src/cpp-template/header/rep.hpp)
• size alias (src/cpp-template/header/size-alias.hpp)
• std::pair の Hash (src/utility/pair-hash.hpp)

Required by

• (offine) Functional Graph 上の頂点 $v$ から $k$ 回移動した先の頂点 (Offline Jump On Functional Graph) (src/graph/functional-graph/offline-query/offline-query-jump-on-functional-graph.hpp)
• (offine) 木のパス $u-v$ 上の $k$ 番目の頂点 (Offline Jump On Tree) (src/graph/tree/offline-query/offline-query-jump-on-tree.hpp)

Verified with

• test/atcoder/abc258_e/offline-algorithm.test.cpp
• test/library-checker/jump_on_tree.test.cpp
• unit-test/graph/offline-query-jump-on-functional-graph.test.cpp

Code

#pragma once

#include "src/cpp-template/header/rep.hpp"
#include "src/cpp-template/header/size-alias.hpp"
#include "src/utility/pair-hash.hpp"

#include <cassert>
#include <optional>
#include <unordered_map>
#include <utility>
#include <vector>

namespace luz {

  template < class G >
  class OfflineLAQuery {
    using graph     = G;
    using cost_type = typename graph::cost_type;

    usize g_size;
    graph g;

    usize query_count;
    std::vector< std::vector< usize > > qs;

    std::vector< bool > visited;
    std::vector< usize > path;

    using query_type = std::pair< usize, usize >;
    std::unordered_map< query_type, std::optional< usize >, PairHash >
        results;

    void bound_check(usize v) const {
      assert(v < g_size);
    }

    void dfs(usize v) {
      visited[v] = true;
      path.emplace_back(v);

      for (const auto &level: qs[v]) {
        if (level < path.size()) {
          results[query_type(v, level)] = path[level];
        }
      }

      for (const auto &e: g[v]) {
        if (visited[e.to]) continue;
        dfs(e.to);
      }

      path.pop_back();
    }

   public:
    explicit OfflineLAQuery() = default;

    explicit OfflineLAQuery(graph &g)
        : g_size(g.size()),
          g(g),
          query_count(0),
          qs(g_size),
          visited(g_size, false) {}

    void add_query(usize v, usize level) {
      bound_check(v);
      qs[v].emplace_back(level);
      query_count++;
    }

    void build(usize root) {
      bound_check(root);
      results.reserve(query_count);
      path.reserve(g_size);
      dfs(root);
    }

    std::optional< usize > la(usize v, usize level) const {
      bound_check(v);
      query_type qi(v, level);
      assert(results.count(qi));
      return (*results.find(qi)).second;
    }
  };

} // namespace luz

#line 2 "src/graph/tree/offline-query/offline-query-level-ancestor.hpp"

#line 2 "src/cpp-template/header/rep.hpp"

#line 2 "src/cpp-template/header/size-alias.hpp"

#include <cstddef>

namespace luz {

  using isize = std::ptrdiff_t;
  using usize = std::size_t;

} // namespace luz
#line 4 "src/cpp-template/header/rep.hpp"

#include <algorithm>

namespace luz {

  struct rep {
    struct itr {
      usize i;
      constexpr itr(const usize i) noexcept: i(i) {}
      void operator++() noexcept {
        ++i;
      }
      constexpr usize operator*() const noexcept {
        return i;
      }
      constexpr bool operator!=(const itr x) const noexcept {
        return i != x.i;
      }
    };
    const itr f, l;
    constexpr rep(const usize f, const usize l) noexcept
        : f(std::min(f, l)),
          l(l) {}
    constexpr auto begin() const noexcept {
      return f;
    }
    constexpr auto end() const noexcept {
      return l;
    }
  };

  struct rrep {
    struct itr {
      usize i;
      constexpr itr(const usize i) noexcept: i(i) {}
      void operator++() noexcept {
        --i;
      }
      constexpr usize operator*() const noexcept {
        return i;
      }
      constexpr bool operator!=(const itr x) const noexcept {
        return i != x.i;
      }
    };
    const itr f, l;
    constexpr rrep(const usize f, const usize l) noexcept
        : f(l - 1),
          l(std::min(f, l) - 1) {}
    constexpr auto begin() const noexcept {
      return f;
    }
    constexpr auto end() const noexcept {
      return l;
    }
  };

} // namespace luz
#line 2 "src/utility/pair-hash.hpp"

#line 4 "src/utility/pair-hash.hpp"

#include <functional>
#include <utility>

namespace luz {

  class PairHash {
    template < typename T >
    usize hash_combine(usize hr, const T &x) const {
      usize h = std::hash< T >()(x);
      return hr ^ (h + (hr << 11) + (hr >> 13));
    }

   public:
    template < typename F, typename S >
    usize operator()(const std::pair< F, S > &p) const {
      return hash_combine(hash_combine(0, p.first), p.second);
    }
  };

} // namespace luz
#line 6 "src/graph/tree/offline-query/offline-query-level-ancestor.hpp"

#include <cassert>
#include <optional>
#include <unordered_map>
#line 11 "src/graph/tree/offline-query/offline-query-level-ancestor.hpp"
#include <vector>

namespace luz {

  template < class G >
  class OfflineLAQuery {
    using graph     = G;
    using cost_type = typename graph::cost_type;

    usize g_size;
    graph g;

    usize query_count;
    std::vector< std::vector< usize > > qs;

    std::vector< bool > visited;
    std::vector< usize > path;

    using query_type = std::pair< usize, usize >;
    std::unordered_map< query_type, std::optional< usize >, PairHash >
        results;

    void bound_check(usize v) const {
      assert(v < g_size);
    }

    void dfs(usize v) {
      visited[v] = true;
      path.emplace_back(v);

      for (const auto &level: qs[v]) {
        if (level < path.size()) {
          results[query_type(v, level)] = path[level];
        }
      }

      for (const auto &e: g[v]) {
        if (visited[e.to]) continue;
        dfs(e.to);
      }

      path.pop_back();
    }

   public:
    explicit OfflineLAQuery() = default;

    explicit OfflineLAQuery(graph &g)
        : g_size(g.size()),
          g(g),
          query_count(0),
          qs(g_size),
          visited(g_size, false) {}

    void add_query(usize v, usize level) {
      bound_check(v);
      qs[v].emplace_back(level);
      query_count++;
    }

    void build(usize root) {
      bound_check(root);
      results.reserve(query_count);
      path.reserve(g_size);
      dfs(root);
    }

    std::optional< usize > la(usize v, usize level) const {
      bound_check(v);
      query_type qi(v, level);
      assert(results.count(qi));
      return (*results.find(qi)).second;
    }
  };

} // namespace luz

Back to top page