This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#include "library/tree/heavy_light_decomposition.hpp"
シグネチャ
using Graph = std::vector<std::vector<int>>; HeavyLightDecomposition(Graph &g, int root = 0)
概要
与えられたグラフに対して HL 分解を行います.
Note. 隣接リストの順序を変更します.具体的には,隣接リストの先頭に Heavy Edge で繋がる子を配置します
制約
時間計算量
木の頂点数を $n$ として,$O(n)$
int lca(int u, int v)
与えられた頂点対の LCA を計算します.
$O(\log n)$
int la(int u, int k, int default_value = -1)
頂点 $u$ の祖先であって,深さが頂点 $u$ よりも丁度 $k$ だけ小さい頂点を返します.つまり,親への辺を丁度 $k$ 回だけ辿って到達する頂点を求めます.ただし,そのような頂点が存在しない場合は,第二引数として渡された default_value を返します.
default_value
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 で累積した結果を計算します.
bin_op
内部的には,$u-v$ パスを添字が連続したいくつかのパスに分割して fold_query により区間和を計算した後,順不同 で結果をマージします.ここでいう添字は元の頂点番号ではなく HLD による置換を作用させた番号であり,fold_query には置換後の添字区間 [l, r) が引数として与えられます.従って,区間和を高速に求める Segment Tree などのデータ構造を外部で用意しておくことが想定されます.
fold_query
[l, r)
なお,頂点に要素が乗っている場合は is_edge_query=false を,辺に要素が乗っている場合は is_edge_query=true を指定します.辺に要素を載せる場合は,木の根以外の頂点に対して,その親への辺に要素が乗っているものとして考えます.
is_edge_query=false
is_edge_query=true
具体的な使用方法についてはテストファイルのコードを見るのが速いと思います.
テンプレート引数
T
Q
(int, int) -> T
F
(T, T) -> T
ただ,これらを明示的に与える必要があることは少ないと思います.
fold_query(l, r) の計算量を $O(f(n))$ として,$O(f(n)\cdot \log n)$.例えば Segment Tree を用いて区間和を取得する場合は $O((\log n) ^ 2)$ となる.
fold_query(l, r)
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 を与える必要があります.
fold_path
fold_query_rev
Q1
Q2
fold_query(l, r) および fold_query_rev(l, r) の計算量を $O(f(n))$ として,$O(f(n)\cdot \log n)$.
fold_query_rev(l, r)
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) が与えられます.
update_query
(int, int) -> void
fold_path と同様,明示的に渡す必要があることは少ないと思います.
update_query(l, r) の計算量を $O(f(n))$ として,$O(f(n)\cdot \log n)$.
update_query(l, r)
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 などのデータ構造を外部で用意しておくことが想定されます.
fold_query(l, r) の計算量を $O(f(n))$ として,$O(f(n))$
template <typename Q> void update_subtree(int u, Q update_query, bool is_edge_query = false)
頂点 $u$ を根とする部分木に含まれる頂点または辺に載せられた要素を更新します.update_query として渡す関数には,引数として置換後の添字の区間 [l, r) が与えられます.
update_query(l, r) の計算量を $O(f(n))$ として,$O(f(n))$.
template <typename T, typename Q> T get_point(int u, Q get_query)
頂点 $u$ に載せられた情報を取得します.get_query として渡す関数には,引数として置換後の添字 $i$ が与えられます.
get_query
(int) -> T
get_query(i) の計算量を $O(f(n))$ として,$O(f(n))$.
get_query(i)
template <typename Q> void update_point(int u, Q update_query)
頂点 $u$ の情報を更新します.update_query として渡す関数には,引数として置換後の添字 $i$ が与えられます.
(int) -> void
update_query(i) の計算量を $O(f(n))$ として,$O(f(n))$.
update_query(i)
#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), siz(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), siz(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 siz[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, siz, par, dep; int dfs(Graph &g, int u, int p) { par[u] = p; siz[u] = 1; int max_size = 0; for (int &v : g[u]) { if (v == p) continue; dep[v] = dep[u] + 1; siz[u] += dfs(g, v, u); if (max_size < siz[v]) { max_size = siz[v]; std::swap(g[u].front(), v); } } return siz[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), siz(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), siz(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 siz[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, siz, par, dep; int dfs(Graph &g, int u, int p) { par[u] = p; siz[u] = 1; int max_size = 0; for (int &v : g[u]) { if (v == p) continue; dep[v] = dep[u] + 1; siz[u] += dfs(g, v, u); if (max_size < siz[v]) { max_size = siz[v]; std::swap(g[u].front(), v); } } return siz[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