comp-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub luzhiled1333/comp-library

:heavy_check_mark: (offine) 木のパス $u-v$ 上の $k$ 番目の頂点 (Offline Jump On Tree)
(src/graph/tree/offline-query/offline-query-jump-on-tree.hpp)

以下では、静的で辺重みのない木について考える。特に断りがない場合、頂点 $u$ と $v$ の距離は $u$, $v$ 間を経由する最小の辺数とする。

木上のパス $u-v$ 上の頂点のうち $u$ からの距離が $k$ であるような頂点を求めるクエリをオフラインで処理する。このようなクエリを $jump(u, v, k)$ と表記する。

Appendix

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

コンストラクタ

OfflineJumpOnTreeQuery(const G &g)

add_query

void add_query(usize u, usize v, usize k)

$jump(u, v, k)$ を求めるクエリを追加する。

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

制約

計算量

build

void build(usize root)

頂点 root を根とする根付き木上での $jump$ クエリを計算する。

root は解に影響しないため何が選ばれても問題はない。

制約

計算量

jump_on_tree

std::optional< usize >
jump_on_tree(usize u, usize v, usize k)

$jump(u, v, k)$ を std::optional でラップして返す。

パス $u-v$ 上に $u$ からの距離が $k$ であるような頂点が存在しない場合は std::nullopt が返る。

使用例

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

OfflineJumpOnTreeQuery jump_query(g);

...

auto jump = jump_query.jump_on_tree(u, v, k);

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

制約

計算量

Depends on

Verified with

Code

#pragma once

#include "src/cpp-template/header/rep.hpp"
#include "src/cpp-template/header/size-alias.hpp"
#include "src/graph/single-source-shortest-path/in-unweighted-graph.hpp"
#include "src/graph/tree/offline-query/offline-query-level-ancestor.hpp"
#include "src/graph/tree/offline-query/offline-query-lowest-common-ancestor.hpp"
#include "src/utility/tuple-hash.hpp"

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

namespace luz {

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

    usize g_size;
    G g;
    OfflineLCAQuery< graph > lca;
    OfflineLAQuery< graph > la;

    using query_type = std::tuple< usize, usize, usize >;

    std::vector< query_type > qs;

    std::vector< query_type > converted_qs;
    std::unordered_map< query_type, std::optional< usize >,
                        TupleHash >
        results;

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

   public:
    explicit OfflineJumpOnTreeQuery(graph &g)
        : g_size(g.size()),
          g(g),
          lca(g),
          la(g) {}

    void add_query(usize start, usize end, usize distance) {
      bound_check(start);
      bound_check(end);
      qs.emplace_back(start, end, distance);
    }

    void build(usize root) {
      bound_check(root);
      for (const auto &[s, t, _]: qs) {
        lca.add_query(s, t);
      }

      lca.build(root);

      sssp::InUnweightedGraph sssp_solver(g, root);
      std::vector< usize > depths = sssp_solver.get_distances();

      converted_qs.reserve(qs.size());
      results.reserve(qs.size());

      for (usize i: rep(0, qs.size())) {
        const auto &[s, t, d] = qs[i];
        usize r               = lca.lca(s, t);
        usize distance_sr     = depths[s] - depths[r];
        usize distance_rt     = depths[t] - depths[r];

        if (d <= distance_sr) {
          converted_qs.emplace_back(i, s,
                                    depths[r] + distance_sr - d);
        } else if (d <= distance_sr + distance_rt) {
          converted_qs.emplace_back(i, t,
                                    depths[r] + d - distance_sr);
        } else {
          results[qs[i]] = std::nullopt;
        }
      }

      for (const auto &[_, v, k]: converted_qs) {
        la.add_query(v, k);
      }

      la.build(root);

      for (const auto &[i, v, k]: converted_qs) {
        results[qs[i]] = la.la(v, k);
      }
    }

    std::optional< usize > jump_on_tree(usize start, usize end,
                                        usize distance) const {
      bound_check(start);
      bound_check(end);
      query_type qi(start, end, distance);
      assert(results.count(qi));
      return (*results.find(qi)).second;
    }
  };

} // namespace luz
#line 2 "src/graph/tree/offline-query/offline-query-jump-on-tree.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/graph/single-source-shortest-path/in-unweighted-graph.hpp"

#line 4 "src/graph/single-source-shortest-path/in-unweighted-graph.hpp"

#include <limits>
#include <queue>
#include <vector>

namespace luz::sssp {

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

    static constexpr usize undefined_ =
        std::numeric_limits< usize >::max();
    static constexpr usize inf_ = std::numeric_limits< usize >::max();

    graph g;
    usize g_size;
    usize source;

    std::vector< usize > ds, parents, ids;

    void bfs(usize s) {
      std::queue< usize > que;

      ds[s] = 0;
      que.emplace(s);

      while (not que.empty()) {
        usize v = que.front();
        que.pop();

        for (const auto &e: g[v]) {
          usize u = e.to;
          if (ds[u] != inf()) {
            continue;
          }

          ds[u] = ds[v] + 1;
          que.emplace(u);
          parents[u] = v;
          ids[u]     = e.id;
        }
      }
    }

   public:
    explicit InUnweightedGraph(const graph &g_, usize source_)
        : g(g_),
          g_size(g.size()),
          source(source_),
          ds(g_size, inf()),
          parents(g_size, undefined()),
          ids(g_size, undefined()) {
      bfs(source);
    }

    graph get_original_graph() const {
      return g;
    }

    inline usize inf() const {
      return inf_;
    }

    inline usize distance(const usize v) const {
      return ds[v];
    }

    inline std::vector< usize > get_distances() const {
      return ds;
    }

    inline usize undefined() const {
      return undefined_;
    }

    inline usize parent(const usize v) const {
      return parents[v];
    }

    inline std::vector< usize > get_parents() const {
      return parents;
    }

    inline usize edge_label(const usize v) const {
      return ids[v];
    }

    inline std::vector< usize > get_edge_labels() const {
      return ids;
    }
  };

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

#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 12 "src/graph/tree/offline-query/offline-query-level-ancestor.hpp"

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-lowest-common-ancestor.hpp"

#line 2 "src/data-structure/disjoint-set-union.hpp"

#line 5 "src/data-structure/disjoint-set-union.hpp"

#line 9 "src/data-structure/disjoint-set-union.hpp"

namespace luz {

  class DisjointSetUnion {
    usize n;

    // vals[v] :=
    //   if v is root node: -1 * component size
    //   otherwise: parent node
    std::vector< isize > vals;

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

    usize impl_leader(usize v) {
      if (vals[v] < 0) return v;
      return vals[v] = leader(vals[v]);
    }

   public:
    DisjointSetUnion() = default;
    explicit DisjointSetUnion(usize n): n(n), vals(n, -1) {}

    usize size() const {
      return n;
    }

    usize leader(usize v) {
      bound_check(v);
      return impl_leader(v);
    }

    bool same(usize u, usize v) {
      bound_check(u), bound_check(v);
      return impl_leader(u) == impl_leader(v);
    }

    usize merge(usize u, usize v) {
      bound_check(u);
      bound_check(v);

      isize x = impl_leader(u);
      isize y = impl_leader(v);
      if (x == y) return x;
      if (-vals[x] < -vals[y]) std::swap(x, y);
      vals[x] += vals[y];
      vals[y] = x;
      return x;
    }

    usize group_size(usize v) {
      bound_check(v);
      return -vals[impl_leader(v)];
    }

    std::vector< std::vector< usize > > groups() {
      std::vector< std::vector< usize > > result(n);

      std::vector< usize > leaders(n), g_sizes(n);
      for (usize v: rep(0, n)) {
        leaders[v] = impl_leader(v);
        g_sizes[leaders[v]]++;
      }
      for (usize v: rep(0, n)) {
        result[v].reserve(g_sizes[v]);
      }
      for (usize v: rep(0, n)) {
        result[leaders[v]].emplace_back(v);
      }

      auto empty_check = [](const std::vector< usize > &vs) {
        return vs.empty();
      };
      result.erase(
          std::remove_if(result.begin(), result.end(), empty_check),
          result.end());

      return result;
    }
  };

} // namespace luz
#line 7 "src/graph/tree/offline-query/offline-query-lowest-common-ancestor.hpp"

#line 12 "src/graph/tree/offline-query/offline-query-lowest-common-ancestor.hpp"

namespace luz {

  template < class G >
  class OfflineLCAQuery {
    using graph     = G;
    using cost_type = typename G::cost_type;
    usize g_size;
    graph g;

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

    DisjointSetUnion dsu;
    std::vector< bool > visited;
    std::vector< usize > ancestors;

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

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

    void dfs(usize v) {
      visited[v]   = true;
      ancestors[v] = v;

      for (const auto &e: g[v]) {
        if (visited[e.to]) continue;
        dfs(e.to);
        dsu.merge(v, e.to);
        ancestors[dsu.leader(v)] = v;
      }

      for (const auto &u: qs[v]) {
        if (not visited[u]) continue;
        results[query_type(u, v)] = results[query_type(v, u)] =
            ancestors[dsu.leader(u)];
      }
    }

   public:
    using Queries = std::vector< std::pair< usize, usize > >;

    OfflineLCAQuery(G &g)
        : g_size(g.size()),
          g(g),
          query_count(0),
          qs(g_size),
          dsu(g_size),
          visited(g_size, false),
          ancestors(g_size) {}

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

    void build(usize root) {
      bound_check(root);
      results.reserve(2 * query_count);
      dfs(root);
    }

    usize lca(usize u, usize v) {
      bound_check(u);
      bound_check(v);
      query_type qi(u, v);
      assert(results.count(qi));
      return results[qi];
    }
  };

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

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

#line 6 "src/utility/tuple-hash.hpp"
#include <tuple>
#line 8 "src/utility/tuple-hash.hpp"

namespace luz::impl_tuple_hash {

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

    template < class Tuple >
    usize operator()(const Tuple &t) const noexcept {
      usize hr = ImplTupleHash< Index - 1 >()(t);
      return hash_combine(std::get< Index - 1 >(t), hr);
    }
  };

  template <>
  class ImplTupleHash< 0 > {
   public:
    template < class Tuple >
    usize operator()([[maybe_unused]] const Tuple &_) const noexcept {
      return 0;
    }
  };

} // namespace luz::impl_tuple_hash

namespace luz {

  class TupleHash {
    template < usize Index >
    using ImplTupleHash = impl_tuple_hash::ImplTupleHash< Index >;

   public:
    template < class... Args >
    usize operator()(const std::tuple< Args... > &t) const {
      using Tuple = std::tuple< Args... >;
      return ImplTupleHash< std::tuple_size< Tuple >::value >()(t);
    }
  };

} // namespace luz
#line 9 "src/graph/tree/offline-query/offline-query-jump-on-tree.hpp"

#line 15 "src/graph/tree/offline-query/offline-query-jump-on-tree.hpp"

namespace luz {

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

    usize g_size;
    G g;
    OfflineLCAQuery< graph > lca;
    OfflineLAQuery< graph > la;

    using query_type = std::tuple< usize, usize, usize >;

    std::vector< query_type > qs;

    std::vector< query_type > converted_qs;
    std::unordered_map< query_type, std::optional< usize >,
                        TupleHash >
        results;

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

   public:
    explicit OfflineJumpOnTreeQuery(graph &g)
        : g_size(g.size()),
          g(g),
          lca(g),
          la(g) {}

    void add_query(usize start, usize end, usize distance) {
      bound_check(start);
      bound_check(end);
      qs.emplace_back(start, end, distance);
    }

    void build(usize root) {
      bound_check(root);
      for (const auto &[s, t, _]: qs) {
        lca.add_query(s, t);
      }

      lca.build(root);

      sssp::InUnweightedGraph sssp_solver(g, root);
      std::vector< usize > depths = sssp_solver.get_distances();

      converted_qs.reserve(qs.size());
      results.reserve(qs.size());

      for (usize i: rep(0, qs.size())) {
        const auto &[s, t, d] = qs[i];
        usize r               = lca.lca(s, t);
        usize distance_sr     = depths[s] - depths[r];
        usize distance_rt     = depths[t] - depths[r];

        if (d <= distance_sr) {
          converted_qs.emplace_back(i, s,
                                    depths[r] + distance_sr - d);
        } else if (d <= distance_sr + distance_rt) {
          converted_qs.emplace_back(i, t,
                                    depths[r] + d - distance_sr);
        } else {
          results[qs[i]] = std::nullopt;
        }
      }

      for (const auto &[_, v, k]: converted_qs) {
        la.add_query(v, k);
      }

      la.build(root);

      for (const auto &[i, v, k]: converted_qs) {
        results[qs[i]] = la.la(v, k);
      }
    }

    std::optional< usize > jump_on_tree(usize start, usize end,
                                        usize distance) const {
      bound_check(start);
      bound_check(end);
      query_type qi(start, end, distance);
      assert(results.count(qi));
      return (*results.find(qi)).second;
    }
  };

} // namespace luz
Back to top page