Heavy Light Decomposition (HLD)
(library/tree/heavy_light_decomposition.hpp)

• View this file on GitHub
• Last update: 2026-06-19 20:35:33+09:00
• Include: #include "library/tree/heavy_light_decomposition.hpp"

コンストラクタ

• シグネチャ

  using Graph = std::vector<std::vector<int>>;
  
  HeavyLightDecomposition(Graph &g, int root = 0)
  

• 概要

  与えられたグラフに対して HL 分解を行います．

  Note. 隣接リストの順序を変更します．具体的には，隣接リストの先頭に Heavy Edge で繋がる子を配置します

  • このようなことを行う理由として，DFS の探索順序と HLD により振られる添字の昇順に頂点を並べた列が一致するという嬉しい性質があります．パスクエリと部分木クエリで添字の置換を共有できるので，両方のタイプのクエリが同時に来るような場合にも対応できるようになります．

• 制約

  • $0\leq \mathrm{root}\lt n$

• 時間計算量

  木の頂点数を $n$ として，$O(n)$

Lowest Common Ancestor (LCA)

• シグネチャ

  int lca(int u, int v)
  

• 概要

  与えられた頂点対の LCA を計算します．

• 制約

  • $0\leq u,v\lt n$

• 時間計算量

  $O(\log n)$

Level Ancestor (LA)

• シグネチャ

  int la(int u, int k, int default_value = -1)
  

• 概要

  頂点 $u$ の祖先であって，深さが頂点 $u$ よりも丁度 $k$ だけ小さい頂点を返します．つまり，親への辺を丁度 $k$ 回だけ辿って到達する頂点を求めます．ただし，そのような頂点が存在しない場合は，第二引数として渡された default_value を返します．

• 制約

  • $0\leq u\lt n$

• 時間計算量

  $O(\log n)$

fold_path

• シグネチャ

  template <typename T, typename Q, typename F>
  T fold_path(int u, int v, T identity, F bin_op, Q fold_query, bool is_edge_query = false)
  

• 概要

  $u-v$ パス上の頂点または辺に載せられた要素を二項演算 bin_op で累積した結果を計算します．

  内部的には，$u-v$ パスを添字が連続したいくつかのパスに分割して fold_query により区間和を計算した後，順不同 で結果をマージします．ここでいう添字は元の頂点番号ではなく HLD による置換を作用させた番号であり，fold_query には置換後の添字区間 [l, r) が引数として与えられます．従って，区間和を高速に求める Segment Tree などのデータ構造を外部で用意しておくことが想定されます．

  なお，頂点に要素が乗っている場合は is_edge_query=false を，辺に要素が乗っている場合は is_edge_query=true を指定します．辺に要素を載せる場合は，木の根以外の頂点に対して，その親への辺に要素が乗っているものとして考えます．

  具体的な使用方法についてはテストファイルのコードを見るのが速いと思います．

• テンプレート引数

  • T: 頂点または辺に載せる要素の型
  • Q: 区間和を求める (int, int) -> T の関数型
  • F: 二項演算 (T, T) -> T の関数型

  ただ，これらを明示的に与える必要があることは少ないと思います．

• 制約

  • $0\leq u,v\lt n$
  • $(T,F)$ は可換モノイド
  • $\mathrm{identity}$ は可換モノイド $(T, F)$ の単位元
  • 任意の $0\leq l\leq r\leq n$ に対して，$\displaystyle \mathrm{fold\_ query}(l,r)=\bigoplus_{i=l}^{r-1}t_i$．ここで $\oplus$ は二項演算であり，$t_i$ は置換後の添字 $i$ に対応する要素．

• 時間計算量

  fold_query(l, r) の計算量を $O(f(n))$ として，$O(f(n)\cdot \log n)$．例えば Segment Tree を用いて区間和を取得する場合は $O((\log n) ^ 2)$ となる．

fold_path_noncommutative

• シグネチャ

  template <typename T, typename Q1, typename Q2, typename F>
  T fold_path_noncommutative(int u, int v, T identity, F bin_op, Q1 fold_query, Q2 fold_query_rev, bool is_edge_query = false)
  

• 概要

  fold_path における可換性の要求を緩和した関数です．可換性を要求しない代わりに，区間和を逆順に求める関数 fold_query_rev を与える必要があります．

• テンプレート引数

  • T: 頂点または辺に載せる要素の型
  • Q1: 区間和を求める (int, int) -> T の関数型
  • Q2: 逆順の区間和を求める (int, int) -> T の関数型
  • F: 二項演算 (T, T) -> T の関数型

• 制約

  • $0\leq u,v\lt n$
  • $(T,F)$ はモノイド (非可換でもよい)
  • $\mathrm{identity}$ はモノイド $(T, F)$ の単位元
  • 任意の $0\leq l\leq r\leq n$ に対して，$\displaystyle \mathrm{fold\_ query}(l,r)=t_l\oplus t_{l+1}\oplus\cdots\oplus t_{r-1}$．
  • 任意の $0\leq l\leq r\leq n$ に対して，$\displaystyle \mathrm{fold\_ query\_ rev}(l,r)=t_{r-1}\oplus\cdots\oplus t_{l+1}\oplus t_l$．

• 時間計算量

  fold_query(l, r) および fold_query_rev(l, r) の計算量を $O(f(n))$ として，$O(f(n)\cdot \log n)$．

update_path

• シグネチャ

  template <typename Q>
  void update_path(int u, int v, Q update_query, bool is_edge_query = false)
  

• 概要

  $u-v$ パス上の頂点または辺に載せられた要素を更新します．update_query として渡す関数は fold_path における fold_query とほぼ同様であり，置換後の添字の区間 [l, r) が与えられます．

• テンプレート引数

  • Q: 区間更新を行う (int, int) -> void の関数型

  fold_path と同様，明示的に渡す必要があることは少ないと思います．

• 制約

  • $0\leq u,v\lt n$

• 時間計算量

  update_query(l, r) の計算量を $O(f(n))$ として，$O(f(n)\cdot \log n)$．

fold_subtree

• シグネチャ

  template <typename T, typename Q>
  T fold_subtree(int u, Q fold_query, bool is_edge_query = false)
  

• 概要

  頂点 $u$ を根とする部分木に含まれる頂点または辺に載せられた要素を 順不同 で畳み込みます．fold_path と同様に，fold_query の引数には置換後の添字の区間 [l, r) が与えられます．

  区間和を高速に求める Segment Tree などのデータ構造を外部で用意しておくことが想定されます．

• テンプレート引数

  • T: 頂点に載せる要素の型
  • Q: 区間和を求める (int, int) -> T の関数型

• 制約

  • $0\leq u\lt n$

• 時間計算量

  fold_query(l, r) の計算量を $O(f(n))$ として，$O(f(n))$

update_subtree

• シグネチャ

  template <typename Q>
  void update_subtree(int u, Q update_query, bool is_edge_query = false)
  

• 概要

  頂点 $u$ を根とする部分木に含まれる頂点または辺に載せられた要素を更新します．update_query として渡す関数には，引数として置換後の添字の区間 [l, r) が与えられます．

• テンプレート引数

  • Q: 区間更新を行う (int, int) -> void の関数型

• 制約

  • $0\leq u\lt n$

• 時間計算量

  update_query(l, r) の計算量を $O(f(n))$ として，$O(f(n))$．

get_point

• シグネチャ

  template <typename T, typename Q>
  T get_point(int u, Q get_query)
  

• 概要

  頂点 $u$ に載せられた情報を取得します．get_query として渡す関数には，引数として置換後の添字 $i$ が与えられます．

• テンプレート引数

  • T: 要素型
  • Q: 点取得を行う (int) -> T の関数型

• 制約

  • $0\leq u\lt n$

• 時間計算量

  get_query(i) の計算量を $O(f(n))$ として，$O(f(n))$．

update_point

• シグネチャ

  template <typename Q>
  void update_point(int u, Q update_query)
  

• 概要

  頂点 $u$ の情報を更新します．update_query として渡す関数には，引数として置換後の添字 $i$ が与えられます．

• テンプレート引数

  • Q: 点更新を行う (int) -> void の関数型

• 制約

  • $0\leq u\lt n$

• 時間計算量

  update_query(i) の計算量を $O(f(n))$ として，$O(f(n))$．

Depends on

• Type Traits (library/type_traits/type_traits.hpp)

Required by

• 指定された頂点たちの最小共通祖先関係を保って木を圧縮してできる補助的な木 (library/tree/auxiliary_tree.hpp)

Verified with

• test/src/tree/heavy_light_decomposition/do_use_segment_tree.test.cpp
• test/src/tree/heavy_light_decomposition/jump_on_tree.test.cpp
• test/src/tree/heavy_light_decomposition/la_based_lowest_common_ancestor.test.cpp
• test/src/tree/heavy_light_decomposition/lowest_common_ancestor.test.cpp
• test/src/tree/heavy_light_decomposition/vertex_add_path_composite.test.cpp
• test/src/tree/heavy_light_decomposition/vertex_add_path_sum.test.cpp
• test/src/tree/heavy_light_decomposition/vertex_add_subtree_sum.test.cpp

Code

#ifndef SUISEN_HLD
#define SUISEN_HLD

#include "library/type_traits/type_traits.hpp"
#include <vector>

namespace suisen {
class HeavyLightDecomposition {
    public:
        template <typename Q>
        using is_point_update_query = std::is_invocable<Q, int>;
        template <typename Q>
        using is_range_update_query = std::is_invocable<Q, int, int>;
        template <typename Q, typename T>
        using is_point_get_query  = std::is_same<std::invoke_result_t<Q, int>, T>;
        template <typename Q, typename T>
        using is_range_fold_query = std::is_same<std::invoke_result_t<Q, int, int>, T>;

        using Graph = std::vector<std::vector<int>>;

        HeavyLightDecomposition() = default;
        HeavyLightDecomposition(Graph &g) : n(g.size()), visit(n), leave(n), head(n), ord(n), subtree_size(n), par(n, -1), dep(n, 0) {
            for (int i = 0; i < n; ++i) if (par[i] < 0) dfs(g, i, -1);
            int time = 0;
            for (int i = 0; i < n; ++i) if (par[i] < 0) hld(g, i, -1, time);
        }
        HeavyLightDecomposition(Graph &g, const std::vector<int> &roots) : n(g.size()), visit(n), leave(n), head(n), ord(n), subtree_size(n), par(n, -1), dep(n, 0) {
            for (int i : roots) dfs(g, i, -1);
            int time = 0;
            for (int i : roots) hld(g, i, -1, time);
        }
        int size() const {
            return n;
        }
        int lca(int u, int v) const {
            for (;; v = par[head[v]]) {
                if (visit[u] > visit[v]) std::swap(u, v);
                if (head[u] == head[v]) return u;
            }
        }
        int la(int u, int k, int default_value = -1) const {
            if (k < 0) return default_value;
            while (u >= 0) {
                int h = head[u];
                if (visit[u] - k >= visit[h]) return ord[visit[u] - k];
                k -= visit[u] - visit[h] + 1;
                u = par[h];
            }
            return default_value;
        }
        int jump(int u, int v, int d, int default_value = -1) const {
            if (d < 0) return default_value;
            const int w = lca(u, v);
            int uw = dep[u] - dep[w];
            if (d <= uw) return la(u, d);
            int vw = dep[v] - dep[w];
            return d <= uw + vw ? la(v, (uw + vw) - d) : default_value;
        }
        int dist(int u, int v) const {
            return dep[u] + dep[v] - 2 * dep[lca(u, v)];
        }
        template <typename T, typename Q, typename F, constraints_t<is_range_fold_query<Q, T>, std::is_invocable_r<T, F, T, T>> = nullptr>
        T fold_path(int u, int v, T identity, F bin_op, Q fold_query, bool is_edge_query = false) const {
            T res = identity;
            for (;; v = par[head[v]]) {
                if (visit[u] > visit[v]) std::swap(u, v);
                if (head[u] == head[v]) break;
                res = bin_op(fold_query(visit[head[v]], visit[v] + 1), res);
            }
            return bin_op(fold_query(visit[u] + is_edge_query, visit[v] + 1), res);
        }
        template <
            typename T, typename Q1, typename Q2, typename F,
            constraints_t<is_range_fold_query<Q1, T>, is_range_fold_query<Q2, T>, std::is_invocable_r<T, F, T, T>> = nullptr
        >
        T fold_path_noncommutative(int u, int v, T identity, F bin_op, Q1 fold_query, Q2 fold_query_rev, bool is_edge_query = false) const {
            T res_u = identity, res_v = identity;
            // a := lca(u, v)
            // res = fold(u -> a) + fold(a -> v)
            while (head[u] != head[v]) {
                if (visit[u] < visit[v]) { // a -> v
                    res_v = bin_op(fold_query(visit[head[v]], visit[v] + 1), res_v);
                    v = par[head[v]];
                } else { // u -> a
                    res_u = bin_op(res_u, fold_query_rev(visit[head[u]], visit[u] + 1));
                    u = par[head[u]];
                }
            }
            if (visit[u] < visit[v]) { // a = u
                res_v = bin_op(fold_query(visit[u] + is_edge_query, visit[v] + 1), res_v);
            } else { // a = v
                res_u = bin_op(res_u, fold_query_rev(visit[v] + is_edge_query, visit[u] + 1));
            }
            return bin_op(res_u, res_v);
        }
        template <typename Q, constraints_t<is_range_update_query<Q>> = nullptr>
        void update_path(int u, int v, Q update_query, bool is_edge_query = false) const {
            for (;; v = par[head[v]]) {
                if (visit[u] > visit[v]) std::swap(u, v);
                if (head[u] == head[v]) break;
                update_query(visit[head[v]], visit[v] + 1);
            }
            update_query(visit[u] + is_edge_query, visit[v] + 1);
        }
        template <typename T, typename Q, constraints_t<is_range_fold_query<Q, T>> = nullptr>
        T fold_subtree(int u, Q fold_query, bool is_edge_query = false) const {
            return fold_query(visit[u] + is_edge_query, leave[u]);
        }
        template <typename Q, constraints_t<is_range_update_query<Q>> = nullptr>
        void update_subtree(int u, Q update_query, bool is_edge_query = false) const {
            update_query(visit[u] + is_edge_query, leave[u]);
        }
        template <typename T, typename Q, constraints_t<is_point_get_query<Q, T>> = nullptr>
        T get_point(int u, Q get_query) const {
            return get_query(visit[u]);
        }
        template <typename Q, constraints_t<is_point_update_query<Q>> = nullptr>
        void update_point(int u, Q update_query) const {
            update_query(visit[u]);
        }
        std::vector<int> inv_ids() const {
            std::vector<int> inv(n);
            for (int i = 0; i < n; ++i) inv[visit[i]] = i;
            return inv;
        }
        int get_visit_time(int u) const {
            return visit[u];
        }
        int get_leave_time(int u) const {
            return leave[u];
        }
        int get_head(int u) const {
            return head[u];
        }
        int get_kth_visited(int k) const {
            return ord[k];
        }
        int get_subtree_size(int u) const {
            return subtree_size[u];
        }
        int get_parent(int u) const {
            return par[u];
        }
        int get_depth(int u) const {
            return dep[u];
        }
        std::vector<int> get_roots() const {
            std::vector<int> res;
            for (int i = 0; i < n; ++i) if (par[i] < 0) res.push_back(i);
            return res;
        }
    private:
        int n;
        std::vector<int> visit, leave, head, ord, subtree_size, par, dep;
        int dfs(Graph &g, int u, int p) {
            par[u] = p;
            subtree_size[u] = 1;
            int max_size = 0;
            for (int &v : g[u]) {
                if (v == p) continue;
                dep[v] = dep[u] + 1;
                subtree_size[u] += dfs(g, v, u);
                if (max_size < subtree_size[v]) {
                    max_size = subtree_size[v];
                    std::swap(g[u].front(), v);
                }
            }
            return subtree_size[u];
        }
        void hld(Graph &g, int u, int p, int &time) {
            visit[u] = time, ord[time] = u, ++time;
            head[u] = p >= 0 and g[p].front() == u ? head[p] : u;
            for (int v : g[u]) {
                if (v != p) hld(g, v, u, time);
            }
            leave[u] = time;
        }
};
} // namespace suisen

#endif // SUISEN_HLD

#line 1 "library/tree/heavy_light_decomposition.hpp"



#line 1 "library/type_traits/type_traits.hpp"



#include <limits>
#include <iostream>
#include <type_traits>

namespace suisen {
    template <typename ...Constraints> using constraints_t = std::enable_if_t<std::conjunction_v<Constraints...>, std::nullptr_t>;

    template <typename T, typename = std::nullptr_t> struct bitnum { static constexpr int value = 0; };
    template <typename T> struct bitnum<T, constraints_t<std::is_integral<T>>> { static constexpr int value = std::numeric_limits<std::make_unsigned_t<T>>::digits; };
    template <typename T> static constexpr int bitnum_v = bitnum<T>::value;
    template <typename T, size_t n> struct is_nbit { static constexpr bool value = bitnum_v<T> == n; };
    template <typename T, size_t n> static constexpr bool is_nbit_v = is_nbit<T, n>::value;

    template <typename T, typename = std::nullptr_t> struct safely_multipliable { using type = T; };
    template <typename T> struct safely_multipliable<T, constraints_t<std::is_signed<T>, is_nbit<T, 32>>> { using type = long long; };
    template <typename T> struct safely_multipliable<T, constraints_t<std::is_signed<T>, is_nbit<T, 64>>> { using type = __int128_t; };
    template <typename T> struct safely_multipliable<T, constraints_t<std::is_unsigned<T>, is_nbit<T, 32>>> { using type = unsigned long long; };
    template <typename T> struct safely_multipliable<T, constraints_t<std::is_unsigned<T>, is_nbit<T, 64>>> { using type = __uint128_t; };
    template <typename T> using safely_multipliable_t = typename safely_multipliable<T>::type;

    template <typename T, typename = void> struct rec_value_type { using type = T; };
    template <typename T> struct rec_value_type<T, std::void_t<typename T::value_type>> {
        using type = typename rec_value_type<typename T::value_type>::type;
    };
    template <typename T> using rec_value_type_t = typename rec_value_type<T>::type;

    template <typename T> class is_iterable {
        template <typename T_> static auto test(T_ e) -> decltype(e.begin(), e.end(), std::true_type{});
        static std::false_type test(...);
    public:
        static constexpr bool value = decltype(test(std::declval<T>()))::value;
    };
    template <typename T> static constexpr bool is_iterable_v = is_iterable<T>::value;
    template <typename T> class is_writable {
        template <typename T_> static auto test(T_ e) -> decltype(std::declval<std::ostream&>() << e, std::true_type{});
        static std::false_type test(...);
    public:
        static constexpr bool value = decltype(test(std::declval<T>()))::value;
    };
    template <typename T> static constexpr bool is_writable_v = is_writable<T>::value;
    template <typename T> class is_readable {
        template <typename T_> static auto test(T_ e) -> decltype(std::declval<std::istream&>() >> e, std::true_type{});
        static std::false_type test(...);
    public:
        static constexpr bool value = decltype(test(std::declval<T>()))::value;
    };
    template <typename T> static constexpr bool is_readable_v = is_readable<T>::value;
} // namespace suisen

#line 5 "library/tree/heavy_light_decomposition.hpp"
#include <vector>

namespace suisen {
class HeavyLightDecomposition {
    public:
        template <typename Q>
        using is_point_update_query = std::is_invocable<Q, int>;
        template <typename Q>
        using is_range_update_query = std::is_invocable<Q, int, int>;
        template <typename Q, typename T>
        using is_point_get_query  = std::is_same<std::invoke_result_t<Q, int>, T>;
        template <typename Q, typename T>
        using is_range_fold_query = std::is_same<std::invoke_result_t<Q, int, int>, T>;

        using Graph = std::vector<std::vector<int>>;

        HeavyLightDecomposition() = default;
        HeavyLightDecomposition(Graph &g) : n(g.size()), visit(n), leave(n), head(n), ord(n), subtree_size(n), par(n, -1), dep(n, 0) {
            for (int i = 0; i < n; ++i) if (par[i] < 0) dfs(g, i, -1);
            int time = 0;
            for (int i = 0; i < n; ++i) if (par[i] < 0) hld(g, i, -1, time);
        }
        HeavyLightDecomposition(Graph &g, const std::vector<int> &roots) : n(g.size()), visit(n), leave(n), head(n), ord(n), subtree_size(n), par(n, -1), dep(n, 0) {
            for (int i : roots) dfs(g, i, -1);
            int time = 0;
            for (int i : roots) hld(g, i, -1, time);
        }
        int size() const {
            return n;
        }
        int lca(int u, int v) const {
            for (;; v = par[head[v]]) {
                if (visit[u] > visit[v]) std::swap(u, v);
                if (head[u] == head[v]) return u;
            }
        }
        int la(int u, int k, int default_value = -1) const {
            if (k < 0) return default_value;
            while (u >= 0) {
                int h = head[u];
                if (visit[u] - k >= visit[h]) return ord[visit[u] - k];
                k -= visit[u] - visit[h] + 1;
                u = par[h];
            }
            return default_value;
        }
        int jump(int u, int v, int d, int default_value = -1) const {
            if (d < 0) return default_value;
            const int w = lca(u, v);
            int uw = dep[u] - dep[w];
            if (d <= uw) return la(u, d);
            int vw = dep[v] - dep[w];
            return d <= uw + vw ? la(v, (uw + vw) - d) : default_value;
        }
        int dist(int u, int v) const {
            return dep[u] + dep[v] - 2 * dep[lca(u, v)];
        }
        template <typename T, typename Q, typename F, constraints_t<is_range_fold_query<Q, T>, std::is_invocable_r<T, F, T, T>> = nullptr>
        T fold_path(int u, int v, T identity, F bin_op, Q fold_query, bool is_edge_query = false) const {
            T res = identity;
            for (;; v = par[head[v]]) {
                if (visit[u] > visit[v]) std::swap(u, v);
                if (head[u] == head[v]) break;
                res = bin_op(fold_query(visit[head[v]], visit[v] + 1), res);
            }
            return bin_op(fold_query(visit[u] + is_edge_query, visit[v] + 1), res);
        }
        template <
            typename T, typename Q1, typename Q2, typename F,
            constraints_t<is_range_fold_query<Q1, T>, is_range_fold_query<Q2, T>, std::is_invocable_r<T, F, T, T>> = nullptr
        >
        T fold_path_noncommutative(int u, int v, T identity, F bin_op, Q1 fold_query, Q2 fold_query_rev, bool is_edge_query = false) const {
            T res_u = identity, res_v = identity;
            // a := lca(u, v)
            // res = fold(u -> a) + fold(a -> v)
            while (head[u] != head[v]) {
                if (visit[u] < visit[v]) { // a -> v
                    res_v = bin_op(fold_query(visit[head[v]], visit[v] + 1), res_v);
                    v = par[head[v]];
                } else { // u -> a
                    res_u = bin_op(res_u, fold_query_rev(visit[head[u]], visit[u] + 1));
                    u = par[head[u]];
                }
            }
            if (visit[u] < visit[v]) { // a = u
                res_v = bin_op(fold_query(visit[u] + is_edge_query, visit[v] + 1), res_v);
            } else { // a = v
                res_u = bin_op(res_u, fold_query_rev(visit[v] + is_edge_query, visit[u] + 1));
            }
            return bin_op(res_u, res_v);
        }
        template <typename Q, constraints_t<is_range_update_query<Q>> = nullptr>
        void update_path(int u, int v, Q update_query, bool is_edge_query = false) const {
            for (;; v = par[head[v]]) {
                if (visit[u] > visit[v]) std::swap(u, v);
                if (head[u] == head[v]) break;
                update_query(visit[head[v]], visit[v] + 1);
            }
            update_query(visit[u] + is_edge_query, visit[v] + 1);
        }
        template <typename T, typename Q, constraints_t<is_range_fold_query<Q, T>> = nullptr>
        T fold_subtree(int u, Q fold_query, bool is_edge_query = false) const {
            return fold_query(visit[u] + is_edge_query, leave[u]);
        }
        template <typename Q, constraints_t<is_range_update_query<Q>> = nullptr>
        void update_subtree(int u, Q update_query, bool is_edge_query = false) const {
            update_query(visit[u] + is_edge_query, leave[u]);
        }
        template <typename T, typename Q, constraints_t<is_point_get_query<Q, T>> = nullptr>
        T get_point(int u, Q get_query) const {
            return get_query(visit[u]);
        }
        template <typename Q, constraints_t<is_point_update_query<Q>> = nullptr>
        void update_point(int u, Q update_query) const {
            update_query(visit[u]);
        }
        std::vector<int> inv_ids() const {
            std::vector<int> inv(n);
            for (int i = 0; i < n; ++i) inv[visit[i]] = i;
            return inv;
        }
        int get_visit_time(int u) const {
            return visit[u];
        }
        int get_leave_time(int u) const {
            return leave[u];
        }
        int get_head(int u) const {
            return head[u];
        }
        int get_kth_visited(int k) const {
            return ord[k];
        }
        int get_subtree_size(int u) const {
            return subtree_size[u];
        }
        int get_parent(int u) const {
            return par[u];
        }
        int get_depth(int u) const {
            return dep[u];
        }
        std::vector<int> get_roots() const {
            std::vector<int> res;
            for (int i = 0; i < n; ++i) if (par[i] < 0) res.push_back(i);
            return res;
        }
    private:
        int n;
        std::vector<int> visit, leave, head, ord, subtree_size, par, dep;
        int dfs(Graph &g, int u, int p) {
            par[u] = p;
            subtree_size[u] = 1;
            int max_size = 0;
            for (int &v : g[u]) {
                if (v == p) continue;
                dep[v] = dep[u] + 1;
                subtree_size[u] += dfs(g, v, u);
                if (max_size < subtree_size[v]) {
                    max_size = subtree_size[v];
                    std::swap(g[u].front(), v);
                }
            }
            return subtree_size[u];
        }
        void hld(Graph &g, int u, int p, int &time) {
            visit[u] = time, ord[time] = u, ++time;
            head[u] = p >= 0 and g[p].front() == u ? head[p] : u;
            for (int v : g[u]) {
                if (v != p) hld(g, v, u, time);
            }
            leave[u] = time;
        }
};
} // namespace suisen

Back to top page