Auxiliary tree (tools/auxiliary_tree.hpp)

View this file on GitHub
View document part on GitHub
Last update: 2025-02-10 20:05:30+09:00
Include: #include "tools/auxiliary_tree.hpp"

It is an auxiliary tree obtained by compressing a tree so that LCA relations of specified vertices are preserved.

License

Author

anqooqie

Constructor

auxiliary_tree graph(std::size_t n);

It creates a graph with $n$ vertices and $0$ edges.

Constraints

$n \geq 1$

Time Complexity

$O(n)$

add_edge

void graph.add_edge(std::size_t u, std::size_t v);

It adds an undirected edge connecting $u$ and $v$ to the graph.

Constraints

graph.build() has not been called ever.
$0 \leq u < n$
$0 \leq v < n$
$u \neq v$

Time Complexity

$O(1)$ amortized

build

void graph.build(std::size_t r);

It asserts that the graph is a rooted tree with root $r$.

Constraints

graph.build() has not been called ever.
The graph is a tree.
$0 \leq r < n$

Time Complexity

$O(n)$

depth

std::size_t graph.depth(std::size_t v);

It returns the number of edges between $r$ and $v$.

Constraints

graph.build() has been called ever.
$0 \leq v < n$

Time Complexity

$O(1)$

lca

std::size_t graph.lca(std::size_t u, std::size_t v);

It returns the lowest common ancestor of two vertices $u$ and $v$.

Constraints

graph.build() has been called ever.
$0 \leq u < n$
$0 \leq v < n$

Time Complexity

$O(1)$

query

template <typename InputIterator>
query_result graph.query(InputIterator begin, InputIterator end);

template <typename Z>
query_result graph.query(std::vector<Z> X);

For a given rooted tree $T = (V, E; r)$ and a subset of its vertices $X \subseteq V$, it returns an auxiliary rooted tree $T’$ that can be obtained by compressing $T$ so that no descendant/ancestor relationship or least common ancestor relationship is lost between the vertices in $X$. More precisely, for each vertex pair $(x, y) \in X^2$, we consider its least common ancestor $z = \mathrm{lca}(x, y)$. The rooted tree $T’ = (V’, E’; r’)$ is the one formed by edging such vertices $V’ = \{\mathrm{lca}(x, y) \mid (x, y) \in X^2\}$ with descendant relations in the original tree $T$.

Constraints

graph.build() has been called ever.
$X$ is a set of integers.
$X \subseteq V$
$X \neq \varnothing$

Time Complexity

$O(|X| \log |X|)$

query_result::size

std::size_t qr.size();

It returns $|V’|$.

Constraints

None

Time Complexity

$O(1)$

query_result::vertices

struct vertices_iterable {
  struct iterator {
    std::size_t operator*();
    iterator& operator++();
    iterator operator++(int):
    friend bool operator==(iterator lhs, iterator rhs);
    friend bool operator!=(iterator lhs, iterator rhs);
  };
  iterator begin();
  iterator end();
};
vertices_iterable qr.vertices();

It returns $V’$.

Constraints

None

Time Complexity

$O(1)$

query_result::root

std::size_t qr.root();

It returns $r’$.

Constraints

None

Time Complexity

$O(1)$

query_result::parent

std::size_t qr.parent(std::size_t v);

It returns the parent of $v$ in $T’$.

Constraints

$v \in V’$
$v \neq r’$

Time Complexity

$O(\log |X|)$

query_result::children

const std::vector<std::size_t>& qr.children(std::size_t v);

It returns the children of $v$ in $T’$.

Constraints

$v \in V’$

Time Complexity

$O(\log |X|)$

Depends on

Verified with

tests/auxiliary_tree.test.cpp

Code

#ifndef TOOLS_AUXILIARY_TREE_HPP
#define TOOLS_AUXILIARY_TREE_HPP

#include <cstddef>
#include <vector>
#include <utility>
#include <algorithm>
#include <stack>
#include <limits>
#include <iterator>
#include <type_traits>
#include "tools/lca.hpp"
#include "tools/less_by.hpp"
#include "tools/less_by_first.hpp"

namespace tools {
  class auxiliary_tree {
    ::tools::lca m_lca;

  public:
    auxiliary_tree() = default;
    explicit auxiliary_tree(const ::std::size_t n) : m_lca(n) {
    }

    ::std::size_t size() const {
      return this->m_lca.size();
    }

    void add_edge(const ::std::size_t u, const ::std::size_t v) {
      this->m_lca.add_edge(u, v);
    }

    void build(const ::std::size_t r) {
      this->m_lca.build(r);
    }

    ::std::size_t depth(const ::std::size_t v) const {
      return this->m_lca.depth(v);
    }

    ::std::size_t lca(const ::std::size_t u, const ::std::size_t v) const {
      return this->m_lca.query(u, v);
    }

    class query_result {
      ::std::vector<::std::pair<::std::size_t, ::std::size_t>> m_parent;
      ::std::vector<::std::vector<::std::size_t>> m_children;
      ::std::size_t m_root;

      template <typename InputIterator>
      query_result(const ::tools::auxiliary_tree& tree, const InputIterator begin, const InputIterator end) {
        ::std::vector<::std::size_t> X(begin, end);
        assert(!X.empty());
        ::std::sort(X.begin(), X.end(), ::tools::less_by([&](const auto v) { return tree.m_lca.internal_in(v); }));

        ::std::stack<::std::size_t> stack;
        auto it = X.begin();
        stack.push(*(it++));
        for (; it != X.end(); ++it) {
          const auto w = tree.lca(stack.top(), *it);
          while (!stack.empty() && tree.depth(w) < tree.depth(stack.top())) {
            const auto u = stack.top();
            stack.pop();
            this->m_parent.emplace_back(u, w);
            if (!stack.empty() && tree.depth(w) < tree.depth(stack.top())) {
              this->m_parent.back().second = stack.top();
            }
          }
          if (stack.empty() || stack.top() != w) {
            stack.push(w);
          }
          stack.push(*it);
        }
        while (!stack.empty()) {
          const auto u = stack.top();
          stack.pop();
          if (stack.empty()) {
            this->m_parent.emplace_back(u, ::std::numeric_limits<::std::size_t>::max());
            this->m_root = u;
          } else {
            this->m_parent.emplace_back(u, stack.top());
          }
        }

        ::std::sort(this->m_parent.begin(), this->m_parent.end(), ::tools::less_by_first{});

        this->m_children.resize(this->m_parent.size());
        for (const auto& [v, p] : this->m_parent) {
          if (v != this->m_root) {
            const auto it = ::std::lower_bound(this->m_parent.begin(), this->m_parent.end(), ::std::make_pair(p, ::std::numeric_limits<::std::size_t>::max()), ::tools::less_by_first{});
            assert(it != this->m_parent.end());
            assert(it->first == p);
            this->m_children[::std::distance(this->m_parent.begin(), it)].push_back(v);
          }
        }
      }

    public:
      class vertices_iterable {
        query_result const *m_qr;

      public:
        class iterator {
          query_result const *m_qr;
          ::std::size_t m_i;

        public:
          using difference_type = ::std::ptrdiff_t;
          using value_type = ::std::size_t;
          using reference = const ::std::size_t&;
          using pointer = const ::std::size_t*;
          using iterator_category = ::std::input_iterator_tag;

          iterator() = default;
          iterator(query_result const * const qr, const ::std::size_t i) : m_qr(qr), m_i(i) {
          }

          reference operator*() const {
            return this->m_qr->m_parent[this->m_i].first;
          }
          iterator& operator++() {
            ++this->m_i;
            return *this;
          }
          iterator operator++(int) {
            const auto self = *this;
            ++*this;
            return self;
          }
          friend bool operator==(const iterator& lhs, const iterator& rhs) {
            assert(lhs.m_qr == rhs.m_qr);
            return lhs.m_i == rhs.m_i;
          }
          friend bool operator!=(const iterator& lhs, const iterator& rhs) {
            return !(lhs == rhs);
          }
        };

        vertices_iterable() = default;
        vertices_iterable(query_result const * const qr) : m_qr(qr) {
        }

        iterator begin() const {
          return iterator(this->m_qr, 0);
        };
        iterator end() const {
          return iterator(this->m_qr, this->m_qr->m_parent.size());
        }
      };

      query_result() = default;

      ::std::size_t size() const {
        return this->m_parent.size();
      }

      vertices_iterable vertices() const {
        return vertices_iterable(this);
      }

      ::std::size_t root() const {
        return this->m_root;
      }

      ::std::size_t parent(const ::std::size_t v) const {
        const auto it = ::std::lower_bound(this->m_parent.begin(), this->m_parent.end(), ::std::make_pair(v, ::std::numeric_limits<::std::size_t>::max()), ::tools::less_by_first{});
        assert(it != this->m_parent.end());
        assert(it->first == v);
        return it->second;
      }

      const ::std::vector<::std::size_t>& children(const ::std::size_t v) const {
        const auto it = ::std::lower_bound(this->m_parent.begin(), this->m_parent.end(), ::std::make_pair(v, ::std::numeric_limits<::std::size_t>::max()), ::tools::less_by_first{});
        assert(it != this->m_parent.end());
        assert(it->first == v);
        return this->m_children[::std::distance(this->m_parent.begin(), it)];
      }

      friend ::tools::auxiliary_tree;
    };

    template <typename InputIterator>
    query_result query(const InputIterator begin, const InputIterator end) const {
      return query_result(*this, begin, end);
    }

    template <typename Z, ::std::enable_if_t<::std::is_integral_v<Z>, ::std::nullptr_t> = nullptr>
    query_result query(const ::std::vector<Z>& X) const {
      return this->query(X.begin(), X.end());
    }
  };
}

#endif

#line 1 "tools/auxiliary_tree.hpp"



#include <cstddef>
#include <vector>
#include <utility>
#include <algorithm>
#include <stack>
#include <limits>
#include <iterator>
#include <type_traits>
#line 1 "tools/lca.hpp"



#include <cstdint>
#line 7 "tools/lca.hpp"
#include <cassert>
#include <numeric>
#line 13 "tools/lca.hpp"
#include <tuple>
#line 1 "tools/ceil.hpp"



#line 1 "tools/is_integral.hpp"



#line 5 "tools/is_integral.hpp"

namespace tools {
  template <typename T>
  struct is_integral : ::std::is_integral<T> {};

  template <typename T>
  inline constexpr bool is_integral_v = ::tools::is_integral<T>::value;
}


#line 1 "tools/is_unsigned.hpp"



#line 5 "tools/is_unsigned.hpp"

namespace tools {
  template <typename T>
  struct is_unsigned : ::std::is_unsigned<T> {};

  template <typename T>
  inline constexpr bool is_unsigned_v = ::tools::is_unsigned<T>::value;
}


#line 8 "tools/ceil.hpp"

namespace tools {
  template <typename M, typename N> requires (
    ::tools::is_integral_v<M> && !::std::is_same_v<::std::remove_cv_t<M>, bool> &&
    ::tools::is_integral_v<N> && !::std::is_same_v<::std::remove_cv_t<N>, bool>)
  constexpr ::std::common_type_t<M, N> ceil(const M x, const N y) noexcept {
    assert(y != 0);
    if (y >= 0) {
      if (x > 0) {
        return (x - 1) / y + 1;
      } else {
        if constexpr (::tools::is_unsigned_v<::std::common_type_t<M, N>>) {
          return 0;
        } else {
          return x / y;
        }
      }
    } else {
      if (x >= 0) {
        if constexpr (::tools::is_unsigned_v<::std::common_type_t<M, N>>) {
          return 0;
        } else {
          return x / y;
        }
      } else {
        return (x + 1) / y + 1;
      }
    }
  }
}


#line 1 "tools/less_by.hpp"



namespace tools {

  template <class F>
  class less_by {
  private:
    F selector;

  public:
    less_by(const F& selector) : selector(selector) {
    }

    template <class T>
    bool operator()(const T& x, const T& y) const {
      return selector(x) < selector(y);
    }
  };
}


#line 1 "tools/ceil_log2.hpp"



#line 1 "tools/bit_width.hpp"



#include <bit>
#line 1 "tools/is_signed.hpp"



#line 5 "tools/is_signed.hpp"

namespace tools {
  template <typename T>
  struct is_signed : ::std::is_signed<T> {};

  template <typename T>
  inline constexpr bool is_signed_v = ::tools::is_signed<T>::value;
}


#line 1 "tools/make_unsigned.hpp"



#line 5 "tools/make_unsigned.hpp"

namespace tools {
  template <typename T>
  struct make_unsigned : ::std::make_unsigned<T> {};

  template <typename T>
  using make_unsigned_t = typename ::tools::make_unsigned<T>::type;
}


#line 10 "tools/bit_width.hpp"

namespace tools {
  template <typename T>
  constexpr int bit_width(T) noexcept;

  template <typename T>
  constexpr int bit_width(const T x) noexcept {
    static_assert(::tools::is_integral_v<T> && !::std::is_same_v<::std::remove_cv_t<T>, bool>);
    if constexpr (::tools::is_signed_v<T>) {
      assert(x >= 0);
      return ::tools::bit_width<::tools::make_unsigned_t<T>>(x);
    } else {
      return ::std::bit_width(x);
    }
  }
}


#line 6 "tools/ceil_log2.hpp"

namespace tools {
  template <typename T>
  constexpr T ceil_log2(T x) noexcept {
    assert(x > 0);
    return ::tools::bit_width(x - 1);
  }
}


#line 1 "tools/floor_log2.hpp"



#line 6 "tools/floor_log2.hpp"

namespace tools {
  template <typename T>
  constexpr T floor_log2(T x) noexcept {
    assert(x > 0);
    return ::tools::bit_width(x) - 1;
  }
}


#line 1 "tools/pow2.hpp"



#line 6 "tools/pow2.hpp"

namespace tools {

  template <typename T, typename ::std::enable_if<::std::is_unsigned<T>::value, ::std::nullptr_t>::type = nullptr>
  constexpr T pow2(const T x) {
    return static_cast<T>(1) << x;
  }

  template <typename T, typename ::std::enable_if<::std::is_signed<T>::value, ::std::nullptr_t>::type = nullptr>
  constexpr T pow2(const T x) {
    return static_cast<T>(static_cast<typename ::std::make_unsigned<T>::type>(1) << static_cast<typename ::std::make_unsigned<T>::type>(x));
  }
}


#line 19 "tools/lca.hpp"

namespace tools {
  class lca {
    using u32 = ::std::uint32_t;
    ::std::vector<::std::vector<u32>> m_graph;
    ::std::vector<u32> m_depth;
    ::std::vector<u32> m_tour;
    ::std::vector<u32> m_in;
    u32 m_block_size;
    ::std::vector<::std::vector<u32>> m_sparse_table;
    ::std::vector<::std::vector<::std::vector<u32>>> m_lookup_table;
    ::std::vector<u32> m_patterns;

    bool built() const {
      return !this->m_depth.empty();
    }

    u32 nblocks() const {
      return ::tools::ceil(this->m_tour.size(), this->m_block_size);
    }

    auto less_by_depth() const {
      return ::tools::less_by([&](const auto v) { return this->m_depth[v]; });
    }

  public:
    lca() = default;
    explicit lca(const ::std::size_t n) : m_graph(n) {
      assert(n >= 1);
    }

    ::std::size_t size() const {
      return this->m_graph.size();
    }

    void add_edge(const ::std::size_t u, const ::std::size_t v) {
      assert(!this->built());
      assert(u < this->size());
      assert(v < this->size());
      assert(u != v);
      this->m_graph[u].push_back(v);
      this->m_graph[v].push_back(u);
    }

    void build(const ::std::size_t r) {
      assert(!this->built());
      assert(::std::accumulate(this->m_graph.begin(), this->m_graph.end(), static_cast<::std::size_t>(0), [](const auto sum, const auto& neighbors) { return sum + neighbors.size(); }) == 2 * (this->size() - 1));

      this->m_depth.assign(this->size(), ::std::numeric_limits<u32>::max());
      this->m_tour.resize(2 * this->size() - 1);
      this->m_in.resize(this->size());

      u32 t = 0;
      ::std::stack<::std::pair<u32, u32>> stack;
      stack.emplace(r, 0);
      while (!stack.empty()) {
        const auto [here, depth] = stack.top();
        stack.pop();
        this->m_tour[t] = here;
        if (this->m_depth[here] == ::std::numeric_limits<u32>::max()) {
          this->m_depth[here] = depth;
          this->m_in[here] = t;
          for (const auto next : this->m_graph[here]) {
            if (this->m_depth[next] == ::std::numeric_limits<u32>::max()) {
              stack.emplace(here, depth);
              stack.emplace(next, depth + 1);
            }
          }
        }
        ++t;
      }

      if (this->size() > 1) {
        this->m_tour.pop_back();
      }

      this->m_block_size = ::std::max<u32>(1, ::tools::ceil(::tools::ceil_log2(this->m_tour.size()), 2));
      this->m_sparse_table.resize(::tools::floor_log2(this->nblocks()) + 1);
      this->m_sparse_table[0].resize(this->nblocks());
      for (u32 b = 0; (b + 1) * this->m_block_size <= this->m_tour.size(); ++b) {
        const auto l = b * this->m_block_size;
        const auto r = ::std::min<u32>(l + this->m_block_size, this->m_tour.size());
        this->m_sparse_table[0][b] = *::std::min_element(this->m_tour.begin() + l, this->m_tour.begin() + r, this->less_by_depth());
      }
      for (u32 h = 1; h < this->m_sparse_table.size(); ++h) {
        this->m_sparse_table[h].resize(this->nblocks() + UINT32_C(1) - (UINT32_C(1) << h));
        for (u32 b = 0; b < this->m_sparse_table[h].size(); ++b) {
          this->m_sparse_table[h][b] = ::std::min(this->m_sparse_table[h - 1][b], this->m_sparse_table[h - 1][b + (UINT32_C(1) << (h - 1))], this->less_by_depth());
        }
      }

      this->m_lookup_table.resize(::tools::pow2(this->m_block_size - 1));
      for (u32 p = 0; p < this->m_lookup_table.size(); ++p) {
        this->m_lookup_table[p].resize(this->m_block_size + 1);
        for (u32 l = 0; l <= this->m_block_size; ++l) {
          this->m_lookup_table[p][l].resize(this->m_block_size + 1);
        }

        ::std::vector<u32> partial_sum(this->m_block_size);
        partial_sum[0] = this->m_block_size;
        for (u32 i = 1; i < this->m_block_size; ++i) {
          partial_sum[i] = partial_sum[i - 1] - UINT32_C(1) + (((p >> (i - 1)) & UINT32_C(1)) << 1);
        }

        for (u32 l = 0; l < this->m_block_size; ++l) {
          this->m_lookup_table[p][l][l + 1] = l;
          for (u32 r = l + 2; r <= this->m_block_size; ++r) {
            this->m_lookup_table[p][l][r] = ::std::min(this->m_lookup_table[p][l][r - 1], r - 1, ::tools::less_by([&](const auto i) { return partial_sum[i]; }));
          }
        }
      }

      this->m_patterns.resize(this->nblocks());
      for (u32 b = 0; b * this->m_block_size < this->m_tour.size(); ++b) {
        const auto l = b * this->m_block_size;
        const auto r = ::std::min<u32>(l + this->m_block_size, this->m_tour.size());
        this->m_patterns[b] = 0;
        for (u32 i = l; i + 1 < r; ++i) {
          this->m_patterns[b] |= static_cast<u32>(this->m_depth[this->m_tour[i]] < this->m_depth[this->m_tour[i + 1]]) << (i - l);
        }
      }
    }

    ::std::size_t depth(const ::std::size_t v) const {
      assert(this->built());
      assert(v < this->size());
      return this->m_depth[v];
    }

    ::std::size_t query(::std::size_t u, ::std::size_t v) const {
      assert(this->built());
      assert(u < this->size());
      assert(v < this->size());

      ::std::tie(u, v) = ::std::minmax({u, v}, ::tools::less_by([&](const auto w) { return this->m_in[w]; }));

      const auto l = this->m_in[u];
      const auto r = this->m_in[v] + UINT32_C(1);
      const auto bl = ::tools::ceil(l, this->m_block_size);
      const auto br = r / this->m_block_size;
      u32 lca;
      if (br < bl) {
        lca = this->m_tour[br * this->m_block_size + this->m_lookup_table[this->m_patterns[br]][l % this->m_block_size][r % this->m_block_size]];
      } else {
        lca = u;
        if (bl < br) {
          const auto h = ::tools::floor_log2(br - bl);
          lca = ::std::min(this->m_sparse_table[h][bl], this->m_sparse_table[h][br - (UINT32_C(1) << h)], this->less_by_depth());
        }
        if (l < bl * this->m_block_size) {
          lca = ::std::min(lca, this->m_tour[(bl - UINT32_C(1)) * this->m_block_size + this->m_lookup_table[this->m_patterns[bl - 1]][l % this->m_block_size][this->m_block_size]], this->less_by_depth());
        }
        if (br * this->m_block_size < r) {
          lca = ::std::min(lca, this->m_tour[br * this->m_block_size + this->m_lookup_table[this->m_patterns[br]][0][r % this->m_block_size]], this->less_by_depth());
        }
      }

      return lca;
    }

    // for tools::auxiliary_tree
    ::std::size_t internal_in(const ::std::size_t v) const {
      assert(this->built());
      assert(v < this->size());
      return this->m_in[v];
    }
  };
}


#line 1 "tools/less_by_first.hpp"



#line 5 "tools/less_by_first.hpp"

namespace tools {

  class less_by_first {
  public:
    template <class T1, class T2>
    bool operator()(const ::std::pair<T1, T2>& x, const ::std::pair<T1, T2>& y) const {
      return x.first < y.first;
    }
  };
}


#line 15 "tools/auxiliary_tree.hpp"

namespace tools {
  class auxiliary_tree {
    ::tools::lca m_lca;

  public:
    auxiliary_tree() = default;
    explicit auxiliary_tree(const ::std::size_t n) : m_lca(n) {
    }

    ::std::size_t size() const {
      return this->m_lca.size();
    }

    void add_edge(const ::std::size_t u, const ::std::size_t v) {
      this->m_lca.add_edge(u, v);
    }

    void build(const ::std::size_t r) {
      this->m_lca.build(r);
    }

    ::std::size_t depth(const ::std::size_t v) const {
      return this->m_lca.depth(v);
    }

    ::std::size_t lca(const ::std::size_t u, const ::std::size_t v) const {
      return this->m_lca.query(u, v);
    }

    class query_result {
      ::std::vector<::std::pair<::std::size_t, ::std::size_t>> m_parent;
      ::std::vector<::std::vector<::std::size_t>> m_children;
      ::std::size_t m_root;

      template <typename InputIterator>
      query_result(const ::tools::auxiliary_tree& tree, const InputIterator begin, const InputIterator end) {
        ::std::vector<::std::size_t> X(begin, end);
        assert(!X.empty());
        ::std::sort(X.begin(), X.end(), ::tools::less_by([&](const auto v) { return tree.m_lca.internal_in(v); }));

        ::std::stack<::std::size_t> stack;
        auto it = X.begin();
        stack.push(*(it++));
        for (; it != X.end(); ++it) {
          const auto w = tree.lca(stack.top(), *it);
          while (!stack.empty() && tree.depth(w) < tree.depth(stack.top())) {
            const auto u = stack.top();
            stack.pop();
            this->m_parent.emplace_back(u, w);
            if (!stack.empty() && tree.depth(w) < tree.depth(stack.top())) {
              this->m_parent.back().second = stack.top();
            }
          }
          if (stack.empty() || stack.top() != w) {
            stack.push(w);
          }
          stack.push(*it);
        }
        while (!stack.empty()) {
          const auto u = stack.top();
          stack.pop();
          if (stack.empty()) {
            this->m_parent.emplace_back(u, ::std::numeric_limits<::std::size_t>::max());
            this->m_root = u;
          } else {
            this->m_parent.emplace_back(u, stack.top());
          }
        }

        ::std::sort(this->m_parent.begin(), this->m_parent.end(), ::tools::less_by_first{});

        this->m_children.resize(this->m_parent.size());
        for (const auto& [v, p] : this->m_parent) {
          if (v != this->m_root) {
            const auto it = ::std::lower_bound(this->m_parent.begin(), this->m_parent.end(), ::std::make_pair(p, ::std::numeric_limits<::std::size_t>::max()), ::tools::less_by_first{});
            assert(it != this->m_parent.end());
            assert(it->first == p);
            this->m_children[::std::distance(this->m_parent.begin(), it)].push_back(v);
          }
        }
      }

    public:
      class vertices_iterable {
        query_result const *m_qr;

      public:
        class iterator {
          query_result const *m_qr;
          ::std::size_t m_i;

        public:
          using difference_type = ::std::ptrdiff_t;
          using value_type = ::std::size_t;
          using reference = const ::std::size_t&;
          using pointer = const ::std::size_t*;
          using iterator_category = ::std::input_iterator_tag;

          iterator() = default;
          iterator(query_result const * const qr, const ::std::size_t i) : m_qr(qr), m_i(i) {
          }

          reference operator*() const {
            return this->m_qr->m_parent[this->m_i].first;
          }
          iterator& operator++() {
            ++this->m_i;
            return *this;
          }
          iterator operator++(int) {
            const auto self = *this;
            ++*this;
            return self;
          }
          friend bool operator==(const iterator& lhs, const iterator& rhs) {
            assert(lhs.m_qr == rhs.m_qr);
            return lhs.m_i == rhs.m_i;
          }
          friend bool operator!=(const iterator& lhs, const iterator& rhs) {
            return !(lhs == rhs);
          }
        };

        vertices_iterable() = default;
        vertices_iterable(query_result const * const qr) : m_qr(qr) {
        }

        iterator begin() const {
          return iterator(this->m_qr, 0);
        };
        iterator end() const {
          return iterator(this->m_qr, this->m_qr->m_parent.size());
        }
      };

      query_result() = default;

      ::std::size_t size() const {
        return this->m_parent.size();
      }

      vertices_iterable vertices() const {
        return vertices_iterable(this);
      }

      ::std::size_t root() const {
        return this->m_root;
      }

      ::std::size_t parent(const ::std::size_t v) const {
        const auto it = ::std::lower_bound(this->m_parent.begin(), this->m_parent.end(), ::std::make_pair(v, ::std::numeric_limits<::std::size_t>::max()), ::tools::less_by_first{});
        assert(it != this->m_parent.end());
        assert(it->first == v);
        return it->second;
      }

      const ::std::vector<::std::size_t>& children(const ::std::size_t v) const {
        const auto it = ::std::lower_bound(this->m_parent.begin(), this->m_parent.end(), ::std::make_pair(v, ::std::numeric_limits<::std::size_t>::max()), ::tools::less_by_first{});
        assert(it != this->m_parent.end());
        assert(it->first == v);
        return this->m_children[::std::distance(this->m_parent.begin(), it)];
      }

      friend ::tools::auxiliary_tree;
    };

    template <typename InputIterator>
    query_result query(const InputIterator begin, const InputIterator end) const {
      return query_result(*this, begin, end);
    }

    template <typename Z, ::std::enable_if_t<::std::is_integral_v<Z>, ::std::nullptr_t> = nullptr>
    query_result query(const ::std::vector<Z>& X) const {
      return this->query(X.begin(), X.end());
    }
  };
}