HLD.cpp

• View this file on GitHub
• Last update: 2023-02-27 10:03:43-03:00

Depends on

• Graph.cpp
• Segtree.cpp
• Traits.cpp
• bits/stdc++.h
• utils/Wrappers.cpp

Required by

• SegtreeHLD.cpp

Code

#ifndef _LIB_HLD
#define _LIB_HLD
#include "Graph.cpp"
#include "Segtree.cpp"
#include "Traits.cpp"
#include <bits/stdc++.h>

namespace lib {
using namespace std;
namespace graph {
namespace {
void empty_lifter(int a, int b, bool inv) {}
} // namespace

template <typename G> struct HLD {
  G graph;
  vector<int> in, out, rin;
  vector<int> L, sz, ch;
  int tempo;

  HLD(const G &g)
      : graph(g), in(g.size()), out(g.size()), rin(g.size()), L(g.size()),
        sz(g.size()), ch(g.size()) {
    build();
  }

  inline int size() const { return graph.size(); }

  void dfs0(int u) {
    sz[u] = 1;
    for (auto &k : graph.adj[u]) {
      int v = graph.edge(k).to;
      L[v] = L[u] + 1;
      dfs0(v);
      if (sz[v] > sz[graph.edge(graph.adj[u][0]).to])
        swap(k, graph.adj[u][0]);
      sz[u] += sz[v];
    }
  }

  void dfs1(int u) {
    in[u] = tempo++;
    rin[in[u]] = u;

    if (graph.adj[u].size() > 0) {
      int v = graph.edge(graph.adj[u][0]).to;
      ch[v] = ch[u];
      dfs1(v);
      for (size_t i = 1; i < graph.adj[u].size(); i++) {
        v = graph.edge(graph.adj[u][i]).to;
        ch[v] = v;
        dfs1(v);
      }
    }
    out[u] = tempo;
  }

  void build() {
    vector<int> roots = graph.roots();
    for (int i : roots)
      dfs0(i);
    tempo = 0;
    for (int i : roots)
      dfs1(i);
  }

  template <typename Lifter>
  inline void operate_on_subtree(int u, Lifter &lifter) {
    lifter(in[u], out[u] - 1, false);
  }

  template <typename T, typename QueryIssuer>
  inline T query_on_subtree(int u, const QueryIssuer &issuer) {
    return issuer(in[u], out[u] - 1);
  }

  template <typename Lifter>
  inline void operate_on_subtree_edges(int u, Lifter &lifter) {
    if (in[u] + 2 <= out[u])
      lifter(in[u] + 1, out[u] - 1, false);
  }

  template <typename T, typename QueryIssuer>
  inline void query_on_subtree_edges(int u, const QueryIssuer &issuer) {
    assert(in[u] + 2 <= out[u]);
    return issuer(in[u] + 1, out[u] - 1);
  }

  template <bool is_edge, typename Lifter>
  int _query_path(int u, int v, Lifter &lifter) {
    int inv = 0;
    for (; ch[u] != ch[v]; u = graph.parent(ch[u])) {
      if (L[ch[u]] < L[ch[v]])
        swap(u, v), inv ^= 1;
      lifter(in[ch[u]], in[u], (bool)inv);
    }
    if (L[u] > L[v])
      swap(u, v), inv ^= 1;
    inv ^= 1;
    if (is_edge && in[u] + 1 <= in[v])
      lifter(in[u] + 1, in[v], (bool)inv);
    else if (!is_edge)
      lifter(in[u], in[v], (bool)inv);
    return u;
  }

  template <typename Lifter>
  inline int operate_on_path(int u, int v, Lifter &lifter) {
    return _query_path<false>(u, v, lifter);
  }

  template <typename Lifter>
  inline int operate_on_path_edges(int u, int v, Lifter &lifter) {
    return _query_path<true>(u, v, lifter);
  }

  template <typename Op> inline void operate_on_vertex(int u, Op &op) {
    op(in[u]);
  }

  template <typename T, typename QueryIssuer>
  inline T query_on_vertex(int u, const QueryIssuer &issuer) {
    return issuer(in[u]);
  }

  inline int lca(int u, int v) {
    return _query_path<false>(u, v, empty_lifter);
  }

  inline int dist(int u, int v) {
    int uv = lca(u, v);
    return L[u] + L[v] - 2 * L[uv];
  }
};

template <typename G> HLD<G> make_hld(const G &graph) { return HLD<G>(graph); }
} // namespace graph
} // namespace lib

#endif

#line 1 "HLD.cpp"


#line 1 "Graph.cpp"


#line 1 "Traits.cpp"


#include <bits/stdc++.h>

namespace lib {
using namespace std;
namespace traits {

template <typename...> struct make_void { using type = void; };

template <typename... T> using void_t = typename make_void<T...>::type;

/// keep caide
template <typename Iterator>
using IteratorCategory = typename iterator_traits<Iterator>::iterator_category;

/// keep caide
template <typename Container>
using IteratorCategoryOf = IteratorCategory<typename Container::iterator>;

/// keep caide
template <typename Iterator>
using IteratorValue = typename iterator_traits<Iterator>::value_type;

/// keep caide
template <typename Container>
using IteratorValueOf = IteratorValue<typename Container::iterator>;

/// keep caide
template <typename Iterator>
using IsRandomIterator =
    is_base_of<random_access_iterator_tag, IteratorCategory<Iterator>>;

/// keep caide
template <typename Iterator>
using IsInputIterator =
    is_base_of<input_iterator_tag, IteratorCategory<Iterator>>;

/// keep caide
template <typename Iterator>
using IsBidirectionalIterator =
    is_base_of<bidirectional_iterator_tag, IteratorCategory<Iterator>>;

/// keep caide
template <typename Container>
using HasRandomIterator =
    is_base_of<random_access_iterator_tag, IteratorCategoryOf<Container>>;

/// keep caide
template <typename Container>
using HasInputIterator =
    is_base_of<input_iterator_tag, IteratorCategoryOf<Container>>;

/// keep caide
template <typename Container>
using HasBidirectionalIterator =
    is_base_of<bidirectional_iterator_tag, IteratorCategoryOf<Container>>;
} // namespace traits
} // namespace lib


#line 1 "utils/Wrappers.cpp"


#line 4 "utils/Wrappers.cpp"

namespace lib {
using namespace std;
namespace graph {
template <typename T> struct Edge {
  const int from, to;
  T data;
};

template <> struct Edge<void> { const int from, to; };

template <typename T> struct VertexWrapper { T data; };

template <> struct VertexWrapper<void> {};
} // namespace graph
} // namespace lib


#line 6 "Graph.cpp"

namespace lib {
using namespace std;
namespace graph {
template <typename V = void, typename E = void, bool Directed = false>
struct GraphImpl {
  typedef GraphImpl<V, E> self_type;
  typedef vector<vector<int>> adj_list;
  typedef Edge<E> edge_type;
  typedef VertexWrapper<V> vertex_type;

  const static bool directed = Directed;

  vector<edge_type> edges;
  adj_list adj;

  vector<vertex_type> vertices;

  class iterator {
  public:
    typedef iterator self_type;
    typedef edge_type value_type;
    typedef edge_type &reference;
    typedef edge_type *pointer;
    typedef std::forward_iterator_tag iterator_category;
    typedef int difference_type;
    iterator(vector<int> *adj, vector<edge_type> *edges, int ptr = 0)
        : adj_(adj), edges_(edges), ptr_(ptr) {}
    self_type operator++() {
      ptr_++;
      return *this;
    }
    self_type operator++(int junk) {
      self_type i = *this;
      ptr_++;
      return i;
    }
    reference operator*() { return (*edges_)[(*adj_)[ptr_]]; }
    pointer operator->() { return &(*edges_)[(*adj_)[ptr_]]; }
    bool operator==(const self_type &rhs) const {
      return adj_ == rhs.adj_ && ptr_ == rhs.ptr_;
    }
    bool operator!=(const self_type &rhs) const { return !(*this == rhs); }

  private:
    vector<int> *adj_;
    vector<edge_type> *edges_;
    int ptr_;
  };

  class const_iterator {
  public:
    typedef const_iterator self_type;
    typedef edge_type value_type;
    typedef edge_type &reference;
    typedef edge_type *pointer;
    typedef std::forward_iterator_tag iterator_category;
    typedef int difference_type;
    const_iterator(vector<int> *adj, vector<edge_type> *edges, int ptr = 0)
        : adj_(adj), edges_(edges), ptr_(ptr) {}
    self_type operator++() {
      ptr_++;
      return *this;
    }
    self_type operator++(int junk) {
      self_type i = *this;
      ptr_++;
      return i;
    }
    const value_type &operator*() { return (*edges_)[(*adj_)[ptr_]]; }
    const value_type *operator->() { return &(*edges_)[(*adj_)[ptr_]]; }
    bool operator==(const self_type &rhs) const {
      return adj_ == rhs.adj_ && ptr_ == rhs.ptr_;
    }
    bool operator!=(const self_type &rhs) const { return !(*this == rhs); }

  private:
    vector<int> *adj_;
    vector<edge_type> *edges_;
    int ptr_;
  };

  struct iterable {
    vector<int> *adj_;
    vector<edge_type> *edges_;

    iterable(vector<int> *adj, vector<edge_type> *edges)
        : adj_(adj), edges_(edges) {}

    inline iterator begin() { return iterator(adj_, edges_); }
    inline iterator end() { return iterator(adj_, edges_, adj_->size()); }

    inline const_iterator cbegin() const {
      return const_iterator(adj_, edges_);
    }
    inline const_iterator cend() const {
      return const_iterator(adj_, edges_, adj_->size());
    }

    inline const_iterator begin() const { return cbegin(); }
    inline const_iterator end() const { return cend(); }

    inline edge_type &operator[](int i) { return (*edges_)[(*adj_)[i]]; }
    inline const edge_type &operator[](int i) const {
      return (*edges_)[(*adj_)[i]];
    }

    inline int index(int i) const { return (*adj_)[i]; }
    inline int size() const { return adj_->size(); }
  };

  GraphImpl() {}

  template <typename S = V,
            typename enable_if<is_void<S>::value>::type * = nullptr>
  GraphImpl(size_t n) : adj(n) {}

  template <typename S = V,
            typename enable_if<!is_void<S>::value>::type * = nullptr>
  GraphImpl(size_t n) : adj(n), vertices(n) {}

  inline iterable n_edges(int i) { return iterable(&adj[i], &edges); }
  inline const iterable n_edges(int i) const {
    return iterable(const_cast<vector<int> *>(&adj[i]),
                    const_cast<vector<edge_type> *>(&edges));
  }
  inline int degree(int i) const { return adj[i].size(); }

  inline int size() const { return adj.size(); }
  inline int edge_size() const { return edges.size(); }
  inline edge_type &edge(int i) { return edges[i]; }
  inline edge_type edge(int i) const { return edges[i]; }

  inline vector<edge_type> all_edges() const { return edges; }

  template <typename S = V,
            typename enable_if<!is_void<S>::value>::type * = nullptr>
  inline S &vertex(int i) {
    return vertices[i];
  }

  template <typename S = V,
            typename enable_if<!is_void<S>::value>::type * = nullptr>
  inline V vertex(int i) const {
    return vertices[i];
  }

  template <typename S = V,
            typename enable_if<is_void<S>::value>::type * = nullptr>
  inline void add_vertex() {
    adj.emplace_back();
  }

  template <typename S = V,
            typename enable_if<!is_void<S>::value>::type * = nullptr>
  inline S &add_vertex() {
    adj.emplace_back();
    return vertices.emplace_back().data;
  }

  template <typename S = E,
            typename enable_if<is_void<S>::value>::type * = nullptr>
  inline void add_edge_(int u, int v) {
    adj[u].push_back(edges.size());
    edges.push_back({u, v});
  }

  template <typename S = E,
            typename enable_if<!is_void<S>::value>::type * = nullptr>
  inline S &add_edge_(int u, int v) {
    adj[u].push_back(edges.size());
    edges.push_back({u, v});
    return edges.back().data;
  }

  void add_2edge(int u, int v) {
    add_edge_(u, v);
    add_edge_(v, u);
  }

  template <typename S = E,
            typename enable_if<!is_void<S>::value>::type * = nullptr>
  inline void add_2edge(int u, int v, const S &data) {
    add_edge_(u, v) = data;
    add_edge_(v, u) = data;
  }

  template <typename S = E,
            typename enable_if<is_void<S>::value && Directed>::type * = nullptr>
  inline void add_edge(int u, int v) {
    adj[u].push_back(edges.size());
    edges.push_back({u, v});
  }

  template <typename S = E,
            typename enable_if<!is_void<S>::value && Directed>::type * = nullptr>
  inline S &add_edge(int u, int v) {
    adj[u].push_back(edges.size());
    edges.push_back({u, v});
    return edges.back().data;
  }
};

template<typename V = void, typename E = void>
using Graph = GraphImpl<V, E, false>;

template<typename V = void, typename E = void>
using DirectedGraph = GraphImpl<V, E, true>;

template <typename V = void, typename E = void>
struct RootedForest : public DirectedGraph<V, E> {
  typedef RootedForest<V, E> self_type;
  using typename DirectedGraph<V, E>::adj_list;
  using typename DirectedGraph<V, E>::edge_type;
  using DirectedGraph<V, E>::DirectedGraph;
  using DirectedGraph<V, E>::adj;
  using DirectedGraph<V, E>::edge;
  vector<int> p, pe;

  void build_parents() {
    if ((int)p.size() == this->size())
      return;

    int n = this->size();
    stack<int> st;
    vector<bool> vis(n);
    p.assign(n, -1), pe.assign(n, -1);
    for (int i = 0; i < n; i++) {
      if (!vis[i]) {
        st.push(i);
        vis[i] = true;
        while (!st.empty()) {
          int u = st.top();
          st.pop();

          for (int k : adj[u]) {
            int v = edge(k).to;
            vis[v] = true;
            st.push(v), pe[v] = k, p[v] = u;
          }
        }
      }
    }
  }

  inline int parent(int i) const {
    const_cast<self_type *>(this)->build_parents();
    return p[i];
  }

  inline bool is_root(int i) const { return parent(i) != -1; }

  inline edge_type &parent_edge(int i) {
    build_parents();
    return edge(pe[i]);
  }
  inline edge_type &parent_edge(int i) const {
    const_cast<self_type *>(this)->build_parents();
    return edge(pe[i]);
  }

  vector<int> roots() const {
    vector<int> res;
    const_cast<self_type *>(this)->build_parents();
    int n = this->size();

    for (int i = 0; i < n; i++)
      if (p[i] == -1)
        res.push_back(i);
    return res;
  }
};

template <typename V = void, typename E = void>
struct RootedTree : public RootedForest<V, E> {
  using typename RootedForest<V, E>::adj_list;
  int root;

  RootedTree(int n, int root) : RootedForest<V, E>(n) {
    assert(n > 0);
    assert(root < n);
    this->root = root;
  }

  RootedTree(const adj_list &adj, int root) : RootedForest<V, E>(adj) {
    assert(adj.size() > 0);
    assert(root < adj.size());
    this->root = root;
  }
};

namespace builders {
namespace {
template <typename F, typename G>
void dfs_rooted_forest(F &forest, const G &graph, int u, vector<bool> &vis) {
  vis[u] = true;
  for (const auto &ed : graph.n_edges(u)) {
    int v = ed.to;
    if (!vis[v]) {
      forest.add_edge(u, v);
      dfs_rooted_forest(forest, graph, v, vis);
    }
  }
}
} // namespace

template <typename A, typename B>
RootedForest<A, B> make_rooted_forest(const Graph<A, B> &graph,
                                      const vector<int> &roots) {
  RootedForest<A, B> res(graph.size());
  vector<bool> vis(graph.size());
  for (int i : roots)
    if (!vis[i])
      dfs_rooted_forest(res, graph, i, vis);
  for (int i = 0; i < graph.size(); i++)
    if (!vis[i])
      dfs_rooted_forest(res, graph, i, vis);
  return res;
}
} // namespace builders
} // namespace graph
} // namespace lib


#line 1 "Segtree.cpp"


#line 4 "Segtree.cpp"

namespace lib {
using namespace std;
namespace seg {
struct LeafBuilder {
  template <typename Node> void operator()(Node &no, int i) const {}
  inline pair<int, int> range() const { return {0, 0}; }
  bool should_build() const { return true; }
};

struct EmptyLeafBuilder : LeafBuilder {
  int n;
  explicit EmptyLeafBuilder(int n) : n(n) {}
  inline pair<int, int> range() const { return {0, n - 1}; }
  bool should_build() const { return true; }
};

struct ImplicitBuilder : LeafBuilder {
  int L, R;
  explicit ImplicitBuilder(int L, int R) : L(L), R(R) {}
  inline pair<int, int> range() const { return {L, R}; }
  bool should_build() const { return false; }
};

// TODO: NOT IMPLEMENTED
template <typename DefaultNode>
struct ImplicitWithDefaultBuilder : LeafBuilder {
  int L, R;
  DefaultNode default_node;
  explicit ImplicitWithDefaultBuilder(int L, int R, DefaultNode def)
      : L(L), R(R), default_node(def) {}

  template <typename Node> inline void operator()(Node &no, int i) const {
    no = default_node;
  }

  inline pair<int, int> range() const { return {L, R}; }
  bool should_build() const { return false; }
};

template <typename RandomIterator> struct RangeLeafBuilder : LeafBuilder {
  RandomIterator begin, end;
  explicit RangeLeafBuilder(RandomIterator begin, RandomIterator end)
      : begin(begin), end(end) {}

  template <typename Node> inline void operator()(Node &no, int i) const {
    no = *(begin + i);
  }

  inline pair<int, int> range() const { return {0, end - begin - 1}; }
};

template <typename F> struct LambdaLeafBuilder : LeafBuilder {
  F f;
  pair<int, int> rng;
  explicit LambdaLeafBuilder(F f, pair<int, int> range)
      : f(f), rng(range) {}

  template <typename Node> inline void operator()(Node &no, int i) const {
    no = f(i);
  }

  inline pair<int, int> range() const { return rng; }
};

EmptyLeafBuilder make_builder(int n) { return EmptyLeafBuilder(n); }

template <typename RandomIterator>
RangeLeafBuilder<RandomIterator> make_builder(RandomIterator begin,
                                              RandomIterator end) {
  return RangeLeafBuilder<RandomIterator>(begin, end);
}

template <typename T>
RangeLeafBuilder<typename vector<T>::const_iterator>
make_builder(const vector<T> &v) {
  return RangeLeafBuilder<typename vector<T>::const_iterator>(v.begin(),
                                                              v.end());
}

template<typename T>
LambdaLeafBuilder<std::function<T(int)>>
make_builder(std::function<T(int)> f, pair<int, int> range) {
  return LambdaLeafBuilder<std::function<T(int)>>(f, range);
}

template <typename T> struct CombineFolder {
  inline T operator()() const { return T(); }

  template <typename Node> inline T operator()(const Node &no) const {
    return T(no);
  }

  inline T operator()(const T &a, const T &b) const { return a + b; }
};

template <typename T> struct EmptyFolder : CombineFolder<T> {
  using CombineFolder<T>::operator();

  template <typename Node> inline T operator()(const Node &no) const {
    return T();
  }
  inline T operator()(const T &a, const T &b) const { return T(); }
};

template <typename T> struct SumFolder : CombineFolder<T> {};

template <typename T> struct ProductFolder : CombineFolder<T> {
  using CombineFolder<T>::operator();
  inline T operator()() const { return T(1); }
  inline T operator()(const T &a, const T &b) const { return a * b; }
};

template <typename T> struct MaxFolder : CombineFolder<T> {
  using CombineFolder<T>::operator();
  inline T operator()() const { return numeric_limits<T>::min(); }
  inline T operator()(const T &a, const T &b) const { return max(a, b); }
};

template <typename T> struct MinFolder : CombineFolder<T> {
  using CombineFolder<T>::operator();
  inline T operator()() const { return numeric_limits<T>::max(); }
  inline T operator()(const T &a, const T &b) const { return min(a, b); }
};

template <typename T> struct SingleValueUpdater {
  T value;
  explicit SingleValueUpdater(T val) : value(val) {}
};

template <typename T> struct SetUpdater : SingleValueUpdater<T> {
  using SingleValueUpdater<T>::SingleValueUpdater;

  template <typename Node> inline void operator()(Node &no) const {
    no = this->value;
  }
};

template <typename T> struct AddUpdater : SingleValueUpdater<T> {
  using SingleValueUpdater<T>::SingleValueUpdater;

  template <typename Node> inline void operator()(Node &no) const {
    no += this->value;
  }
};

template <typename T> struct MultUpdater : SingleValueUpdater<T> {
  using SingleValueUpdater<T>::SingleValueUpdater;

  template <typename Node> inline void operator()(Node &no) const {
    no *= this->value;
  }
};

struct EmptyPushdown {
  template<typename Node>
  inline bool dirty(const Node& no) const { return false; }

  template<typename Node>
  inline void operator()(Node& no, int l, int r, 
                  Node* ln, Node* rn) const {}
};

template<typename Node>
struct Active : public Node {
  bool active_ = false;
  Active& operator=(const Node& no) {
    Node::operator=(no);
    return *this;
  }
  bool is_active() const { return active_; }
  Active& activate() {
    active_ = true;
    return *this;
  }
  Active& deactivate() {
    active_ = false;
    return *this;
  }
  void toggle() {
    active_ = !active_;
  }
  friend Active<Node> operator+(const Active<Node>& a, const Active<Node>& b) {
    if(!a.active_) return b;
    else if(!b.active_) return a;
    Active<Node> res;
    res = Node(a) + Node(b);
    return res.activate();
  }
};

template <typename T>
struct ActiveUpdater {
  bool flag;

  ActiveUpdater(bool f) : flag(f) {}

  template <typename Node> inline void operator()(Node &no) const {
    no.active_ = flag;
  }
};
}  // namespace seg
}  // namespace lib


#line 7 "HLD.cpp"

namespace lib {
using namespace std;
namespace graph {
namespace {
void empty_lifter(int a, int b, bool inv) {}
} // namespace

template <typename G> struct HLD {
  G graph;
  vector<int> in, out, rin;
  vector<int> L, sz, ch;
  int tempo;

  HLD(const G &g)
      : graph(g), in(g.size()), out(g.size()), rin(g.size()), L(g.size()),
        sz(g.size()), ch(g.size()) {
    build();
  }

  inline int size() const { return graph.size(); }

  void dfs0(int u) {
    sz[u] = 1;
    for (auto &k : graph.adj[u]) {
      int v = graph.edge(k).to;
      L[v] = L[u] + 1;
      dfs0(v);
      if (sz[v] > sz[graph.edge(graph.adj[u][0]).to])
        swap(k, graph.adj[u][0]);
      sz[u] += sz[v];
    }
  }

  void dfs1(int u) {
    in[u] = tempo++;
    rin[in[u]] = u;

    if (graph.adj[u].size() > 0) {
      int v = graph.edge(graph.adj[u][0]).to;
      ch[v] = ch[u];
      dfs1(v);
      for (size_t i = 1; i < graph.adj[u].size(); i++) {
        v = graph.edge(graph.adj[u][i]).to;
        ch[v] = v;
        dfs1(v);
      }
    }
    out[u] = tempo;
  }

  void build() {
    vector<int> roots = graph.roots();
    for (int i : roots)
      dfs0(i);
    tempo = 0;
    for (int i : roots)
      dfs1(i);
  }

  template <typename Lifter>
  inline void operate_on_subtree(int u, Lifter &lifter) {
    lifter(in[u], out[u] - 1, false);
  }

  template <typename T, typename QueryIssuer>
  inline T query_on_subtree(int u, const QueryIssuer &issuer) {
    return issuer(in[u], out[u] - 1);
  }

  template <typename Lifter>
  inline void operate_on_subtree_edges(int u, Lifter &lifter) {
    if (in[u] + 2 <= out[u])
      lifter(in[u] + 1, out[u] - 1, false);
  }

  template <typename T, typename QueryIssuer>
  inline void query_on_subtree_edges(int u, const QueryIssuer &issuer) {
    assert(in[u] + 2 <= out[u]);
    return issuer(in[u] + 1, out[u] - 1);
  }

  template <bool is_edge, typename Lifter>
  int _query_path(int u, int v, Lifter &lifter) {
    int inv = 0;
    for (; ch[u] != ch[v]; u = graph.parent(ch[u])) {
      if (L[ch[u]] < L[ch[v]])
        swap(u, v), inv ^= 1;
      lifter(in[ch[u]], in[u], (bool)inv);
    }
    if (L[u] > L[v])
      swap(u, v), inv ^= 1;
    inv ^= 1;
    if (is_edge && in[u] + 1 <= in[v])
      lifter(in[u] + 1, in[v], (bool)inv);
    else if (!is_edge)
      lifter(in[u], in[v], (bool)inv);
    return u;
  }

  template <typename Lifter>
  inline int operate_on_path(int u, int v, Lifter &lifter) {
    return _query_path<false>(u, v, lifter);
  }

  template <typename Lifter>
  inline int operate_on_path_edges(int u, int v, Lifter &lifter) {
    return _query_path<true>(u, v, lifter);
  }

  template <typename Op> inline void operate_on_vertex(int u, Op &op) {
    op(in[u]);
  }

  template <typename T, typename QueryIssuer>
  inline T query_on_vertex(int u, const QueryIssuer &issuer) {
    return issuer(in[u]);
  }

  inline int lca(int u, int v) {
    return _query_path<false>(u, v, empty_lifter);
  }

  inline int dist(int u, int v) {
    int uv = lca(u, v);
    return L[u] + L[v] - 2 * L[uv];
  }
};

template <typename G> HLD<G> make_hld(const G &graph) { return HLD<G>(graph); }
} // namespace graph
} // namespace lib

Back to top page