graph/centroid_path_decomposition.hpp

• View this file on GitHub
• Last update: 2024-10-27 21:04:38+09:00
• Include: #include "graph/centroid_path_decomposition.hpp"
• Link: https://kazuma8128.hatenablog.com/entry/2018/07/16/010500#fn-96e76557

Depends on

• debugger/debug.hpp
• internal/concepts.hpp
• internal/dev_env.hpp
• internal/exception.hpp
• internal/resolving_rank.hpp
• internal/type_traits.hpp
• internal/types.hpp
• macro/basic.hpp
• macro/overload.hpp
• numeric/int128.hpp
• snippet/internal/types.hpp
• snippet/iterations.hpp
• template/debug.hpp

Required by

• include/all.hpp
• include/graph_theory.hpp

Verified with

• verify/aizu-online-judge/itp1_1_a/0001.test.cpp

Code

#pragma once


#include <vector>
#include <utility>
#include <functional>

#include "snippet/iterations.hpp"

#include "internal/dev_env.hpp"
#include "internal/types.hpp"

#include "template/debug.hpp"

namespace uni {

// Thanks to: https://kazuma8128.hatenablog.com/entry/2018/07/16/010500#fn-96e76557
class centroid_path_decomposition {
    using size_type = internal::size_t;

  private:
    std::vector<std::vector<size_type>> graph;

  public:
    std::vector<size_type> in, out, size, head, parent;

  private:
    size_type _cur = 0;

    void _erase_parent(const size_type v, const size_type p) noexcept(NO_EXCEPT) {
        this->parent[v] = p;
        ITRR(nv, graph[v]) {
            if(nv == this->graph[v].back()) break;
            if(nv == p) std::swap(nv, this->graph[v].back());
            this->_erase_parent(nv, v);
        }
        this->graph[v].pop_back();
    }

    void _race_size(const size_type v) noexcept(NO_EXCEPT) {
        ITRR(nv, this->graph[v]) {
            this->_race_size(nv);
            this->size[v] += this->size[nv];
            if(this->size[nv] > this->size[this->graph[v].front()]) std::swap(nv, this->graph[v].front());
        }
    }

    void _race_path(const size_type v) noexcept(NO_EXCEPT) {
        this->in[v] = this->_cur++;
        ITR(nv, this->graph[v]) {
            this->head[nv] = (nv == this->graph[v].front() ? this->head[v] : nv);
            this->_race_path(nv);
        }
        this->out[v] = this->_cur;
    }

  public:
    template<class Graph>
    centroid_path_decomposition(const Graph& _graph, const size_type root = 0) noexcept(NO_EXCEPT)
      : graph(_graph.size()), in(_graph.size(), -1), out(_graph.size(), -1), size(_graph.size(), 1), head(_graph.size()), parent(_graph.size(), -1)
    {
        REP(v, _graph.size()) ITR(nv, _graph[v]) { this->graph[v].push_back(nv); }
        this->build(root);
    }

    void build(const size_type root = 0) noexcept(NO_EXCEPT) {
        ITR(v, this->graph[root]) this->_erase_parent(v, root);
        this->_race_size(root);
        this->head[root] = root;
        this->_race_path(root);
    }

    size_type id(const size_type v) noexcept(NO_EXCEPT) { return this->in[v]; }

    size_type lca(size_type u, size_type v) const noexcept(NO_EXCEPT) {
        while(true) {
            if(this->in[u] > this->in[v]) std::swap(u, v);
            if(this->head[u] == this->head[v]) return u;
            v = this->parent[this->head[v]];
        }
    }

    template<class F>
    void edges_on_path(size_type u, size_type v, F&& f) noexcept(NO_EXCEPT) {
        while(true) {
            if(this->in[u] > this->in[v]) std::swap(u, v);
            if(this->head[u] != this->head[v]) {
                f(this->in[this->head[v]] - 1, this->in[v]);
                v = this->parent[this->head[v]];
            } else {
                if(u != v) f(this->in[u], this->in[v]);
                break;
            }
        }
    }

    template<class F>
    void nodes_on_path(size_type u, size_type v, F&& f) noexcept(NO_EXCEPT) {
        while (true) {
            if (this->in[u] > this->in[v]) std::swap(u, v);
            f(std::max(this->in[this->head[v]], this->in[u]), this->in[v]);
            if (this->head[u] != this->head[v])
                v = this->parent[this->head[v]];
            else {
                break;
            }
        }
    }

    template<class F>
    void subtree(const size_type v, F&& f) noexcept(NO_EXCEPT) { f(this->in[v], this->out[v]); }
};


} // namespace uni

#line 2 "graph/centroid_path_decomposition.hpp"


#include <vector>
#include <utility>
#include <functional>

#line 2 "snippet/iterations.hpp"

#include <type_traits>
#line 2 "macro/overload.hpp"

#define $OVERLOAD2(arg0, arg1, cmd, ...) cmd
#define $OVERLOAD3(arg0, arg1, arg2, cmd, ...) cmd
#define $OVERLOAD4(arg0, arg1, arg2, arg3, cmd, ...) cmd
#define $OVERLOAD5(arg0, arg1, arg2, arg3, arg4, cmd, ...) cmd
#define $OVERLOAD6(arg0, arg1, arg2, arg3, arg4, arg5, cmd, ...) cmd
#line 2 "macro/basic.hpp"

#define TO_STRING_AUX(x) #x
#define TO_STRING(x) TO_STRING_AUX(x)

#define CONCAT_AUX(x, y) x##y
#define CONCAT(x, y) CONCAT_AUX(x, y)

#define UNPAREN_AUX(...) __VA_ARGS__
#define UNPAREN(...) __VA_ARGS__
#line 6 "snippet/iterations.hpp"


#define LOOP(n) REPI(CONCAT(_$, __COUNTER__), n)

#define REPI(i,n) for(std::remove_cvref_t<decltype(n)> i=0, CONCAT(i, $)=(n); i<CONCAT(i, $); ++i)
#define REPF(i,l,r) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>> i=(l), CONCAT(i, $)=(r); i<CONCAT(i, $); ++i)
#define REPIS(i,l,r,s) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>,std::remove_cvref_t<decltype(s)>> i=(l), CONCAT(i, $)=(r); i<CONCAT(i, $); i+=(s))

#define REPR(i,n) for(auto i=(n); --i>=0;)
#define REPB(i,l,r) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>> i=(r), CONCAT(i, $)=(l); --i>=CONCAT(i, $);)
#define REPRS(i,l,r,s) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>,std::remove_cvref_t<decltype(s)>> i=(l)+((r)-(l)-1)/(s)*(s), CONCAT(i, $)=(l); i>=CONCAT(i, $); (i-=(s)))

#define REP(...) $OVERLOAD4(__VA_ARGS__, REPIS, REPF, REPI, LOOP)(__VA_ARGS__)
#define REPD(...) $OVERLOAD4(__VA_ARGS__, REPRS, REPB, REPR)(__VA_ARGS__)

#define FORO(i,n) for(int i=0, CONCAT(i, $)=static_cast<int>(n); i<=CONCAT(i, $); ++i)
#define FORI(i,l,r) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>> i=(l), CONCAT(i, $)=(r); i<=CONCAT(i, $); ++i)
#define FORIS(i,l,r,s) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>,std::remove_cvref_t<decltype(s)>> i=(l), CONCAT(i, $)=(r); i<=CONCAT(i, $); i+=(s))

#define FORRO(i,n) for(auto i=(n); i>=0; --i)
#define FORR(i,l,r) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>> i=(r), CONCAT(i, $)=(l); i>=CONCAT(i, $); --i)
#define FORRS(i,l,r,s) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>,std::remove_cvref_t<decltype(s)>> i=(l)+((r)-(l))/(s)*(s), CONCAT(i, $)=(l); i>=CONCAT(i, $); i-=(s))

#define FOR(...) $OVERLOAD4(__VA_ARGS__, FORIS, FORI, FORO)(__VA_ARGS__)
#define FORD(...) $OVERLOAD4(__VA_ARGS__, FORRS, FORR, FORRO)(__VA_ARGS__)

#define ITR1(e0,v) for(const auto &e0 : (v))
#define ITRP1(e0,v) for(auto e0 : (v))
#define ITRR1(e0,v) for(auto &e0 : (v))

#define ITR2(e0,e1,v) for(const auto [e0, e1] : (v))
#define ITRP2(e0,e1,v) for(auto [e0, e1] : (v))
#define ITRR2(e0,e1,v) for(auto &[e0, e1] : (v))

#define ITR3(e0,e1,e2,v) for(const auto [e0, e1, e2] : (v))
#define ITRP3(e0,e1,e2,v) for(auto [e0, e1, e2] : (v))
#define ITRR3(e0,e1,e2,v) for(auto &[e0, e1, e2] : (v))

#define ITR4(e0,e1,e2,e3,v) for(const auto [e0, e1, e2, e3] : (v))
#define ITRP4(e0,e1,e2,e3,v) for(auto [e0, e1, e2, e3] : (v))
#define ITRR4(e0,e1,e2,e3,v) for(auto &[e0, e1, e2, e3] : (v))

#define ITR5(e0,e1,e2,e3,e4,v) for(const auto [e0, e1, e2, e3, e4] : (v))
#define ITRP5(e0,e1,e2,e3,e4,v) for(auto [e0, e1, e2, e3, e4] : (v))
#define ITRR5(e0,e1,e2,e3,e4,v) for(auto &[e0, e1, e2, e3, e4] : (v))

#define ITR(...) $OVERLOAD6(__VA_ARGS__, ITR5, ITR4, ITR3, ITR2, ITR1)(__VA_ARGS__)
#define ITRP(...) $OVERLOAD6(__VA_ARGS__, ITRP5, ITRP4, ITRP3, ITRP2, ITRP1)(__VA_ARGS__)
#define ITRR(...) $OVERLOAD6(__VA_ARGS__, ITRR5, ITRR4, ITRR3, ITRR2, ITRR1)(__VA_ARGS__)
#line 9 "graph/centroid_path_decomposition.hpp"

#line 2 "internal/dev_env.hpp"


#ifdef LOCAL_JUDGE
    inline constexpr bool DEV_ENV = true;
    inline constexpr bool NO_EXCEPT = false;
#else
    inline constexpr bool DEV_ENV = false;
    inline constexpr bool NO_EXCEPT = true;
#endif // LOCAL_JUDGE


#if __cplusplus >= 202100L
    #define CPP20 true
    #define CPP23 true
#elif __cplusplus >= 202002L
    #define CPP20 true
    #define CPP23 false
#else
    #define CPP20 false
    #define CPP23 false
#endif
#line 2 "internal/types.hpp"

#include <cstdint>

namespace uni {

namespace internal {


using size_t = std::int64_t;

using int128_t = __int128_t;
using uint128_t = __uint128_t;


} // namesapce internal

} // namespace uni
#line 12 "graph/centroid_path_decomposition.hpp"

#line 2 "template/debug.hpp"


#ifdef LOCAL_JUDGE

#define DEBUGGER_ENABLED
#define DEBUGGER_COLORED_OUTPUT 1

#endif

#include <string>
#line 2 "debugger/debug.hpp"


#include <iostream>
#include <limits>
#include <iterator>
#include <string_view>
#include <sstream>
#include <array>
#line 11 "debugger/debug.hpp"
#include <cstring>
#line 13 "debugger/debug.hpp"
#include <bitset>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#line 22 "debugger/debug.hpp"
#include <iomanip>
#include <ranges>
#include <concepts>
#line 26 "debugger/debug.hpp"


#line 2 "numeric/int128.hpp"


#include <cctype>
#include <cassert>
#line 8 "numeric/int128.hpp"
#include <algorithm>

#line 2 "snippet/internal/types.hpp"

#line 4 "snippet/internal/types.hpp"

namespace uni {


using i16 = std::int16_t;
using u16 = std::uint16_t;

using i32 = std::int32_t;
using u32 = std::uint32_t;

using i64 = std::int64_t;
using u64 = std::uint64_t;

#ifdef __GNUC__

using i128 = __int128_t;
using u128 = __uint128_t;

using f128 = __float128;

#endif

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;
using ld = long double;


} // namespace uni
#line 12 "numeric/int128.hpp"

#line 14 "numeric/int128.hpp"


namespace std {


template<class C, class S>
auto& operator>>(std::basic_istream<C, S>& in, uni::i128& v) noexcept(NO_EXCEPT) {
    std::string str; in >> str;
    v = 0;
    bool negative = (str[0] == '-');
    REP(d, std::ranges::next(str.begin(), negative), str.end()) {
        assert(std::isdigit(*d));
        v = v * 10 + *d - '0';
    }
    if(negative) v *= -1;
    return in;
}


template<class C, class S>
auto& operator>>(std::basic_istream<C, S>& in, uni::u128& v) noexcept(NO_EXCEPT) {
    std::string str; in >> str;
    v = 0U;
    assert(str[0] != '-');
    REP(d, str.begin(), str.end()) {
        assert(std::isdigit(*d));
        v = v * 10U + *d - '0';
    }
    return in;
}

template<class C, class S>
auto& operator<<(std::basic_ostream<C, S>& out, uni::i128 v) noexcept(NO_EXCEPT) {
    if(v == 0) return out << 0;
    if(v < 0) out << '-', v *= -1;
    std::string str;
    while(v > 0) str += static_cast<char>(v%10) + '0', v /= 10;
    std::reverse(str.begin(), str.end());
    return out << str;
}

template<class C, class S>
auto& operator<<(std::basic_ostream<C, S>& out, uni::u128 v) noexcept(NO_EXCEPT) {
    if(v == 0) return out << 0U;
    std::string str;
    while(v > 0) str += static_cast<char>(v%10U) + '0', v /= 10U;
    std::reverse(str.begin(), str.end());
    return out << str;
}


}
#line 29 "debugger/debug.hpp"

#line 2 "internal/type_traits.hpp"


#line 9 "internal/type_traits.hpp"


#line 12 "internal/type_traits.hpp"


namespace uni {

namespace internal {


template<class... Ts> struct tuple_or_pair { using type = std::tuple<Ts...>; };
template<class T, class U> struct tuple_or_pair<T,U> { using type = std::pair<T, U>; };
template <class... Ts> using tuple_or_pair_t = typename tuple_or_pair<Ts...>::type;

template<class T>
constexpr std::underlying_type_t<T> to_underlying(const T& v) noexcept(NO_EXCEPT) {
    return static_cast<std::underlying_type_t<T>>(v);
}


template<class T, class... Ts>
using are_same = std::conjunction<std::is_same<T, Ts>...>;

template<class T, class... Ts>
inline constexpr bool are_same_v = are_same<T, Ts...>::value;


template<class T, class... Ts>
using is_same_as_any_of = std::disjunction<std::is_same<T, Ts>...>;

template<class T, class... Ts>
inline constexpr bool is_same_as_any_of_v = is_same_as_any_of<T, Ts...>::value;

template<class T, class... Ts>
concept same_as_any_of = is_same_as_any_of_v<T, Ts...>;


template<class Base, class... Derived>
using is_base_of_all = std::conjunction<std::is_base_of<Base, Derived>...>;

template<class Base, class... Derived>
inline constexpr bool is_base_of_all_v = is_base_of_all<Base, Derived...>::value;


template<class Base, class... Derived>
using is_base_of_any = std::disjunction<std::is_base_of<Base, Derived>...>;

template<class Base, class... Derived>
inline constexpr bool is_base_of_any_v = is_base_of_any<Base, Derived...>::value;


template<class T> struct remove_cvref {
  using type = typename std::remove_cv_t<std::remove_reference_t<T>>;
};

template<class T> using remove_cvref_t = typename remove_cvref<T>::type;


template<class T> struct literal_operator { static constexpr const char* value = ""; };

template<> struct literal_operator<unsigned> { static constexpr const char* value = "U"; };
template<> struct literal_operator<long> { static constexpr const char* value = "L"; };
template<> struct literal_operator<unsigned long> { static constexpr const char* value = "UL"; };
template<> struct literal_operator<long long> { static constexpr const char* value = "LL"; };
template<> struct literal_operator<unsigned long long> { static constexpr const char* value = "ULL"; };


template<> struct literal_operator<float> { static constexpr const char* value = "F"; };
template<> struct literal_operator<double> { static constexpr const char* value = "D"; };
template<> struct literal_operator<long double> { static constexpr const char* value = "LD"; };

#ifdef __SIZEOF_INT128__

template<> struct literal_operator<__int128_t> { static constexpr const char* value = "LLL"; };
template<> struct literal_operator<__uint128_t> { static constexpr const char* value = "ULLL"; };

#endif

template<class T> inline constexpr auto literal_operator_v = literal_operator<T>::value;


template <std::size_t N, typename... Types>
struct nth_type {};

template <class Head, class... Tail>
struct nth_type<0, Head, Tail...> {
	using type = Head;
};

template <std::size_t N, class Head, class... Tail>
struct nth_type<N, Head, Tail...> : public nth_type<N - 1, Tail...> {};

template <std::size_t N, typename... Types>
using nth_type_t = typename nth_type<N, Types...>::type;


template<template <class...> class, class> struct is_template_of : std::false_type {};
template<template <class...> class Template, class... Args> struct is_template_of<Template, Template<Args...>> : std::true_type {};

template<template <class...> class Template, class Type>
inline constexpr bool is_template_of_v = is_template_of<Template, Type>::value;

template<class Type, template <class...> class Template>
concept substituted_from = is_template_of_v<Template, Type>;

template<template <class...> class Base, class Derived>
struct _is_basic_tempalte_of
{
    template<class... Ts>
    static constexpr std::true_type  test(const Base<Ts...> *);

    static constexpr std::false_type test(...);

    using type = decltype(test(std::declval<Derived*>()));
};


template<template <class...> class Base, class Derived>
using is_basic_tempalte_of = _is_basic_tempalte_of<Base, Derived>::type;

template<template <class...> class Base, class Derived>
inline constexpr bool is_basic_tempalte_of_v = is_basic_tempalte_of<Base, Derived>::value;

template<class Derived, template <class...> class Base>
concept derived_from_template = is_basic_tempalte_of_v<Base, Derived>;


template<class T> struct is_loggable {
    template<class U>
    static constexpr auto External(U &&v) -> decltype(_debug(v), std::true_type());
    static constexpr std::false_type External(...);

    template<class U>
    static constexpr auto Member(U &&v) -> decltype(v._debug(), std::true_type());
    static constexpr std::false_type Member(...);

    static constexpr bool value = (
      decltype(External(std::declval<T>()))::value ||
      decltype(Member(std::declval<T>()))::value
    );

};

template<class T>
inline constexpr auto is_loggable_v = is_loggable<T>::value;

template<class T>
concept loggable = is_loggable_v<T>;


template<class T> struct _has_iterator {
    template<class U>
    static constexpr auto ADL(U &&v) -> decltype(begin(v), end(v), std::true_type());
    static constexpr std::false_type ADL(...);

    template<class U>
    static constexpr auto STL(U &&v) -> decltype(std::begin(v), std::end(v), std::true_type());
    static constexpr std::false_type STL(...);

    template<class U>
    static constexpr auto Member(U &&v) -> decltype(v.begin(), v.end(), std::true_type());
    static constexpr std::false_type Member(...);
};

template<class T> struct has_iterator {
    struct ADL : decltype(_has_iterator<T>::ADL(std::declval<T>())) {};
    struct STL : decltype(_has_iterator<T>::STL(std::declval<T>())) {};
    struct Member : decltype(_has_iterator<T>::Member(std::declval<T>())) {};

    static constexpr auto adl_v = ADL::value;
    static constexpr auto stl_v = STL::value;
    static constexpr auto member_v = Member::value;
};


template<class T>
struct is_iterable {
    static constexpr bool value =  has_iterator<T>::adl_v || has_iterator<T>::stl_v || has_iterator<T>::member_v;
};

template<class T>
inline constexpr auto is_iterable_v = is_iterable<T>::value;

template<class T>
concept iterable = is_iterable_v<T>;

namespace iterator_resolver {


template<class T>
inline constexpr auto begin(T&& v) noexcept(NO_EXCEPT) {
    static_assert(is_iterable_v<T>);
    if constexpr(has_iterator<T>::member_v) {
        return v.begin();
    }
    else {  // ADL
        using std::begin;
        return begin(std::forward<T>(v));
    }
}

template<class T>
inline constexpr auto end(T&& v) noexcept(NO_EXCEPT) {
    static_assert(is_iterable_v<T>);
    if constexpr(has_iterator<T>::member_v) {
        return v.end();
    }
    else {  // ADL
        using std::end;
        return end(std::forward<T>(v));
    }
}


};


template<class C> using iterator_t = decltype(iterator_resolver::begin(std::declval<C&>()));

template<class C> using container_size_t = decltype(std::size(std::declval<C&>()));


template<bool Const, class T>
using maybe_const_t = std::conditional_t<Const, const T, T>;


template<class T> using with_ref = T&;
template<class T> concept can_reference = requires { typename with_ref<T>; };


} // namespace internal

}  // namespace uni
#line 2 "internal/concepts.hpp"


#line 9 "internal/concepts.hpp"


namespace uni {

namespace internal {


template<class R, class T>
concept convertibel_range = std::convertible_to<std::ranges::range_value_t<R>, T>;


template<class T, class V>
concept item_or_convertible_range = std::convertible_to<T, V> || convertibel_range<T, V>;


template<class Structure>
concept available =
    requires () {
        typename Structure;
    };

template<
    template<class...> class Structure,
    class... TemplateParameters
>
concept available_with = available<Structure<TemplateParameters...>>;


template<class T> concept arithmetic = std::is_arithmetic_v<T>;
template<class T> concept pointer = std::is_pointer_v<T>;
template<class T> concept structural = std::is_class_v<T>;


template<class Large, class Small>
concept has_double_digits_of = (std::numeric_limits<Large>::digits == 2 * std::numeric_limits<Small>::digits);


template<class Large, class Small>
concept has_more_digits_than = (std::numeric_limits<Large>::digits > std::numeric_limits<Small>::digits);

template<class Large, class Small>
concept has_or_more_digits_than = (std::numeric_limits<Large>::digits >= std::numeric_limits<Small>::digits);


template<class T>
concept has_static_zero = requires { T::zero; };

template<class T>
concept has_static_one = requires { T::one; };


template<class L, class R = L>
concept weakly_bitand_calcurable = requires (L lhs, R rhs) { lhs & rhs; };

template<class L, class R = L>
concept weakly_bitor_calcurable = requires (L lhs, R rhs) { lhs | rhs; };

template<class L, class R = L>
concept weakly_bitxor_calcurable = requires (L lhs, R rhs) { lhs ^ rhs; };

template<class L, class R = L>
concept weakly_addable = requires (L lhs, R rhs) { lhs + rhs; };

template<class L, class R = L>
concept weakly_subtractable = requires (L lhs, R rhs) { lhs - rhs; };

template<class L, class R = L>
concept weakly_multipliable = requires (L lhs, R rhs) { lhs * rhs; };

template<class L, class R = L>
concept weakly_divisable = requires (L lhs, R rhs) { lhs / rhs; };

template<class L, class R = L>
concept weakly_remainder_calculable = requires (L lhs, R rhs) { lhs % rhs; };


template<class L, class R = L>
concept weakly_bitand_assignable = requires (L lhs, R rhs) { lhs += rhs; };

template<class L, class R = L>
concept weakly_bitor_assignable = requires (L lhs, R rhs) { lhs |= rhs; };

template<class L, class R = L>
concept weakly_bitxor_assignable = requires (L lhs, R rhs) { lhs ^= rhs; };

template<class L, class R = L>
concept weakly_addition_assignable = requires (L lhs, R rhs) { lhs += rhs; };

template<class L, class R = L>
concept weakly_subtraction_assignable = requires (L lhs, R rhs) { lhs -= rhs; };

template<class L, class R = L>
concept weakly_multipliation_assignalbe = requires (L lhs, R rhs) { lhs *= rhs; };

template<class L, class R = L>
concept weakly_division_assignable = requires (L lhs, R rhs) { lhs /= rhs; };

template<class L, class R = L>
concept weakly_remainder_assignable = requires (L lhs, R rhs) { lhs /= rhs; };


template<class L, class R = L>
concept bitand_calculable =
    weakly_bitand_calcurable<L, R> &&
    weakly_bitand_calcurable<std::invoke_result_t<std::bit_and<>&, L, R>, R> &&
    weakly_bitand_calcurable<L, std::invoke_result_t<std::bit_and<>&, L, R>> &&
    weakly_bitand_calcurable<std::invoke_result_t<std::bit_and<>&, L, R>, std::invoke_result_t<std::bit_and<>&, L, R>>;

template<class L, class R = L>
concept bitor_calculable =
    weakly_bitor_calcurable<L, R> &&
    weakly_bitor_calcurable<std::invoke_result_t<std::bit_or<>&, L, R>, R> &&
    weakly_bitor_calcurable<L, std::invoke_result_t<std::bit_or<>&, L, R>> &&
    weakly_bitor_calcurable<std::invoke_result_t<std::bit_or<>&, L, R>, std::invoke_result_t<std::bit_or<>&, L, R>>;

template<class L, class R = L>
concept bitxor_calculable =
    weakly_bitxor_calcurable<L, R> &&
    weakly_bitxor_calcurable<std::invoke_result_t<std::bit_xor<>&, L, R>, R> &&
    weakly_bitxor_calcurable<L, std::invoke_result_t<std::bit_xor<>&, L, R>> &&
    weakly_bitxor_calcurable<std::invoke_result_t<std::bit_xor<>&, L, R>, std::invoke_result_t<std::bit_xor<>&, L, R>>;

template<class L, class R = L>
concept addable =
    weakly_addable<L, R> &&
    weakly_addable<std::invoke_result_t<std::plus<>&, L, R>, R> &&
    weakly_addable<L, std::invoke_result_t<std::plus<>&, L, R>> &&
    weakly_addable<std::invoke_result_t<std::plus<>&, L, R>, std::invoke_result_t<std::plus<>&, L, R>>;

template<class L, class R = L>
concept subtractable =
    weakly_subtractable<L, R> &&
    weakly_subtractable<std::invoke_result_t<std::minus<>&, L, R>, R> &&
    weakly_subtractable<L, std::invoke_result_t<std::minus<>&, L, R>> &&
    weakly_subtractable<std::invoke_result_t<std::minus<>&, L, R>, std::invoke_result_t<std::minus<>&, L, R>>;

template<class L, class R = L>
concept multipliable =
    weakly_multipliable<L, R> &&
    weakly_multipliable<std::invoke_result_t<std::multiplies<>&, L, R>, R> &&
    weakly_multipliable<L, std::invoke_result_t<std::multiplies<>&, L, R>> &&
    weakly_multipliable<std::invoke_result_t<std::multiplies<>&, L, R>, std::invoke_result_t<std::multiplies<>&, L, R>>;

template<class L, class R = L>
concept divisable =
    weakly_divisable<L, R> &&
    weakly_divisable<std::invoke_result_t<std::divides<>&, L, R>, R> &&
    weakly_divisable<L, std::invoke_result_t<std::divides<>&, L, R>> &&
    weakly_divisable<std::invoke_result_t<std::divides<>&, L, R>, std::invoke_result_t<std::divides<>&, L, R>>;

template<class L, class R = L>
concept remainder_calculable =
    weakly_remainder_calculable<L, R> &&
    weakly_remainder_calculable<std::invoke_result_t<std::modulus<>&, L, R>, R> &&
    weakly_remainder_calculable<L, std::invoke_result_t<std::modulus<>&, L, R>> &&
    weakly_remainder_calculable<std::invoke_result_t<std::modulus<>&, L, R>, std::invoke_result_t<std::modulus<>&, L, R>>;


template<class L, class R = L>
concept bitand_assignable =
    weakly_bitand_assignable<L, R> &&
    weakly_bitand_assignable<std::invoke_result_t<std::bit_and<>&, L, R>, R> &&
    weakly_bitand_assignable<L, std::invoke_result_t<std::bit_and<>&, L, R>> &&
    weakly_bitand_assignable<std::invoke_result_t<std::bit_and<>&, L, R>, std::invoke_result_t<std::bit_and<>&, L, R>>;

template<class L, class R = L>
concept bitor_assignable =
    weakly_bitor_calcurable<L, R> &&
    weakly_bitor_calcurable<std::invoke_result_t<std::bit_or<>&, L, R>, R> &&
    weakly_bitor_calcurable<L, std::invoke_result_t<std::bit_or<>&, L, R>> &&
    weakly_bitor_calcurable<std::invoke_result_t<std::bit_or<>&, L, R>, std::invoke_result_t<std::bit_or<>&, L, R>>;

template<class L, class R = L>
concept bitxor_assignable =
    weakly_bitxor_calcurable<L, R> &&
    weakly_bitxor_calcurable<std::invoke_result_t<std::bit_xor<>&, L, R>, R> &&
    weakly_bitxor_calcurable<L, std::invoke_result_t<std::bit_xor<>&, L, R>> &&
    weakly_bitxor_calcurable<std::invoke_result_t<std::bit_xor<>&, L, R>, std::invoke_result_t<std::bit_xor<>&, L, R>>;

template<class L, class R = L>
concept addition_assignable =
    weakly_addition_assignable<L, R> &&
    weakly_addition_assignable<std::remove_cvref_t<std::invoke_result_t<std::plus<>&, L, R>>, R> &&
    weakly_addition_assignable<L, std::invoke_result_t<std::plus<>&, L, R>> &&
    weakly_addition_assignable<std::remove_cvref_t<std::invoke_result_t<std::plus<>&, L, R>>, std::invoke_result_t<std::plus<>&, L, R>>;

template<class L, class R = L>
concept subtraction_assignable =
    weakly_subtraction_assignable<L, R> &&
    weakly_subtraction_assignable<std::remove_cvref_t<std::invoke_result_t<std::minus<>&, L, R>>, R> &&
    weakly_subtraction_assignable<L, std::invoke_result_t<std::minus<>&, L, R>> &&
    weakly_subtraction_assignable<std::remove_cvref_t<std::invoke_result_t<std::minus<>&, L, R>>, std::invoke_result_t<std::minus<>&, L, R>>;

template<class L, class R = L>
concept multipliation_assignalbe =
    weakly_multipliation_assignalbe<L, R> &&
    weakly_multipliation_assignalbe<std::remove_cvref_t<std::invoke_result_t<std::multiplies<>&, L, R>>, R> &&
    weakly_multipliation_assignalbe<L, std::invoke_result_t<std::multiplies<>&, L, R>> &&
    weakly_multipliation_assignalbe<std::remove_cvref_t<std::invoke_result_t<std::multiplies<>&, L, R>>, std::invoke_result_t<std::multiplies<>&, L, R>>;

template<class L, class R = L>
concept division_assignable =
    weakly_division_assignable<L, R> &&
    weakly_division_assignable<std::remove_cvref_t<std::invoke_result_t<std::divides<>&, L, R>>, R> &&
    weakly_division_assignable<L, std::invoke_result_t<std::divides<>&, L, R>> &&
    weakly_division_assignable<std::remove_cvref_t<std::invoke_result_t<std::divides<>&, L, R>>, std::invoke_result_t<std::divides<>&, L, R>>;

template<class L, class R = L>
concept remainder_assignable =
    weakly_remainder_assignable<L, R> &&
    weakly_remainder_assignable<std::remove_cvref_t<std::invoke_result_t<std::modulus<>&, L, R>>, R> &&
    weakly_remainder_assignable<L, std::invoke_result_t<std::modulus<>&, L, R>> &&
    weakly_remainder_assignable<std::remove_cvref_t<std::invoke_result_t<std::modulus<>&, L, R>>, std::invoke_result_t<std::modulus<>&, L, R>>;


template<class T>
concept weakly_incrementable =
    std::movable<T> &&
    requires (T v) {
        { ++v } -> std::same_as<T&>;
        v++;
    };

template<class T>
concept weakly_decrementable =
    std::movable<T> &&
    requires (T v) {
        { --v } -> std::same_as<T&>;
        v--;
    };


template<class T>
concept incrementable =
    std::regular<T> &&
    weakly_incrementable<T> &&
    requires (T v) {
        { v++ } -> std::same_as<T>;
    };

template<class T>
concept decrementable =
    std::regular<T> &&
    weakly_decrementable<T> &&
    requires (T v) {
        { v-- } -> std::same_as<T>;
    };


template<class L, class R = L>
concept weakly_arithmetic_operable =
    weakly_addable<L, R> &&
    weakly_subtractable<L, R> &&
    weakly_multipliable<L, R> &&
    weakly_divisable<L, R>;

template<class L, class R = L>
concept weakly_arithmetic_operation_assignable =
    weakly_addition_assignable<L, R> &&
    weakly_subtraction_assignable<L, R> &&
    weakly_multipliation_assignalbe<L, R> &&
    weakly_division_assignable<L, R>;

template<class L, class R = L>
concept arithmetic_operable =
    weakly_arithmetic_operable<L, R> &&
    addable<L, R> &&
    subtractable<L, R> &&
    multipliable<L, R> &&
    divisable<L, R>;

template<class L, class R = L>
concept arithmetic_operation_assignable =
    weakly_arithmetic_operation_assignable<L, R> &&
    addition_assignable<L, R> &&
    subtraction_assignable<L, R> &&
    multipliation_assignalbe<L, R> &&
    division_assignable<L, R>;


template<class T>
concept unary_addable =
    requires (T v) {
        { +v } -> std::same_as<T>;
    };

template<class T>
concept unary_subtractable =
    requires (T v) {
        { -v } -> std::same_as<T>;
    };


template<class T>
concept numeric =
    std::regular<T> &&
    arithmetic_operable<T> &&
    arithmetic_operation_assignable<T> &&
    weakly_incrementable<T> &&
    unary_addable<T> &&
    unary_subtractable<T>;


} // namespace internal

} // namespace uni
#line 2 "internal/resolving_rank.hpp"


namespace uni {

namespace internal {


template<int P> struct resolving_rank : resolving_rank<P-1> {};
template<> struct resolving_rank<0> {};


} // namespace internal

} // namespace uni
#line 2 "internal/exception.hpp"


namespace uni {

namespace internal {


template<class... T> inline constexpr bool EXCEPTION_ON_TYPE = false;
template<auto T> inline constexpr bool EXCEPTION_ON_VALUE = false;


} // namespace internal

} // namespace uni
#line 34 "debugger/debug.hpp"

#include <typeinfo>
#include <cxxabi.h>


namespace debugger {


template<class T>
auto _debug (T&& val) -> decltype(val._debug()) {
    return val._debug();
}


std::ostream *cdebug = &std::clog;


#ifdef DEBUGGER_COLORED_OUTPUT

constexpr std::string COLOR_LINE = "\033[3;35m";
constexpr std::string COLOR_IDENTIFIER = "\033[32m";
constexpr std::string COLOR_INIT = "\033[m";
constexpr std::string COLOR_STRING = "\033[33m";
constexpr std::string COLOR_TYPE = "\033[34m";
constexpr std::string COLOR_NUMERIC = "\033[36m";
constexpr std::string COLOR_LITERAL_OPERATOR = "\033[31m";

#else

constexpr std::string COLOR_LINE = "";
constexpr std::string COLOR_IDENTIFIER = "";
constexpr std::string COLOR_INIT = "";
constexpr std::string COLOR_STRING = "";
constexpr std::string COLOR_TYPE = "";
constexpr std::string COLOR_NUMERIC = "";
constexpr std::string COLOR_LITERAL_OPERATOR = "";

#endif

using Brackets = std::pair<std::string, std::string>;


template<class T>
std::string dump(T&&);


template<class T>
const std::string get_type_name(T&& val) {
    const char* const name = typeid(std::forward<T>(val)).name();
    int status = -4;
    char* const demangled_name = abi::__cxa_demangle(name, NULL, NULL, &status);
    std::string res{name};
    if (status == 0) {
        res = std::string(demangled_name);
        free(demangled_name);
    }

    return COLOR_TYPE + res + COLOR_INIT;
}

struct debug_t : std::string {
    using std::string::string;
    debug_t(const std::string& str) {
        this->assign(str);
    }
};


template<size_t N, class T>
void dump_tuple_impl([[maybe_unused]] T&& val, std::stringstream &res) {
    if constexpr(N < std::tuple_size_v<std::remove_cvref_t<T>>) {
        res << dump(std::get<N>(val));
        if constexpr(N < std::tuple_size_v<std::remove_cvref_t<T>> - 1) res << ", ";
        dump_tuple_impl<N + 1>(std::forward<T>(val), res);
    }
}


template<std::ranges::input_range R>
std::string dump_range_impl(R&& range, const Brackets& brcs = { "[", "]" }, const std::string& spl = ", ") {
    std::stringstream res;

    res << brcs.first << " ";

    auto itr = std::ranges::begin(range);
    auto end = std::ranges::end(std::forward<R>(range));

    while(itr != end) {
        if(std::ranges::next(itr) == end) res << dump(*itr) << " ";
        else res << dump(*itr) << spl;
        ++itr;
    }

    res << brcs.second ;

    return res.str();
}


std::string dump_debug_t(debug_t info) {
    return info;
}


struct dump_primitive_like {
    std::string operator()(std::nullptr_t) const {
        return COLOR_INIT;
    }

    template<uni::internal::pointer T>
    std::string operator()(const T ptr) const {
        return dump(*ptr);
    }

    template<class T>
        requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::basic_string>
    std::string operator()(T&& val) const {
        std::stringstream res;
        res << COLOR_STRING << "`" << val << "`" << COLOR_INIT;
        return res.str();
    }

    std::string operator()(const char val) const {
        std::stringstream res;
        res << COLOR_STRING << "\'" << val << "\'" << COLOR_INIT;
        return res.str();
    }

    std::string operator()(const char val[]) const {
        std::stringstream res;
        res << COLOR_STRING << "\"" << val << "\"" <<  COLOR_INIT;
        return res.str();
    }

    std::string operator()(const unsigned char val) const {
        std::stringstream res;
        res << COLOR_NUMERIC << static_cast<int>(val) << COLOR_INIT;
        return res.str();
    }


    std::string operator()(const bool val) const {
        std::stringstream res;
        res << COLOR_NUMERIC << (val ? "true" : "false" ) << COLOR_INIT;
        return res.str();
    }


    template<uni::internal::arithmetic T>
    std::string operator()(const T val) const {
        std::stringstream res;
        res << std::setprecision(std::numeric_limits<T>::digits10) << val;

        auto str = res.str();

        std::string dst = "";
        while(str.length() > 3) {
            dst = ',' + str.substr(str.length() - 3, 3) + dst;
            str = str.substr(0, str.length() - 3);
        }

        return COLOR_NUMERIC + str + dst + COLOR_LITERAL_OPERATOR + uni::internal::literal_operator_v<T> + COLOR_INIT;
    };

    template<class T>
        requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::optional>
    std::string operator()(T&& val) const {
        if(val.has_value()) return dump(*val);
        return COLOR_TYPE + "invalid" + COLOR_INIT;
    }
};


struct dump_bitset {
    template<std::size_t N>
    std::string operator()(const std::bitset<N>& val) const {
        std::stringstream res;
        res << COLOR_NUMERIC << val.to_string() << COLOR_INIT;
        return res.str();
    }
};


struct dump_has_val {
    template<class T>
        requires requires (T val) { val.val(); }
    std::string operator()(T&& val) const {
        return dump(val.val());
    }
};


struct dump_iterator {
    template<std::input_or_output_iterator I>
    std::string operator()(I&& itr) const {
        return COLOR_TYPE + "<iterator> " + COLOR_INIT+ dump(*itr);
    }
};


struct dump_wrapper {
    template<class T>
        requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::map>
    std::string operator()(T&& val) const {
        return dump_range_impl(val, Brackets("{", "}"));
    }

    template<class T>
        requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::multimap>
    std::string operator()(T&& val) const {
        return dump_range_impl(val, Brackets("{", "}"));
    }

    template<class T>
        requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::unordered_map>
    std::string operator()(T&& val) const {
        return dump_range_impl(val, Brackets("{", "}"));
    }

    template<class T>
        requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::unordered_multimap>
    std::string operator()(T&& val) const {
        return dump_range_impl(val, Brackets("{", "}"));
    }

    template<class T>
        requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::set>
    std::string operator()(T&& val) const {
        return dump_range_impl(val, Brackets("{", "}"));
    }

    template<class T>
        requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::multiset>
    std::string operator()(T&& val) const {
        return dump_range_impl(val, Brackets("{", "}"));
    }

    template<class T>
        requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::unordered_set>
    std::string operator()(T&& val) const {
        return dump_range_impl(val, Brackets("{", "}"));
    }

    template<class T>
        requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::unordered_multiset>
    std::string operator()(T&& val) const {
        return dump_range_impl(val, Brackets("{", "}"));
    }

    template<class T>
        requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::valarray>
    std::string operator()(T&& val) const {
        return dump_range_impl(val, Brackets("[", "]"));
    }

    template<class T>
        requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::vector>
    std::string operator()(T&& val) const {
        return dump_range_impl(val, Brackets("[", "]"));
    }

    template<class T>
        requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::deque>
    std::string operator()(T&& val) const {
        return dump_range_impl(val, Brackets("[", "]"));
    }


    template<uni::internal::derived_from_template<std::queue> T>
    std::string operator()(T val) const {
        std::vector<typename T::value_type> vec;

        while(!val.empty()) vec.emplace_back(val.front()), val.pop();

        return dump_range_impl(vec, Brackets("<", ">"));
    }

    template<uni::internal::derived_from_template<std::stack> T>
    std::string operator()(T val) const {
        std::vector<typename T::value_type> vec;

        while(!val.empty()) vec.emplace_back(val.top()), val.pop();
        std::ranges::reverse(vec);

        return dump_range_impl(vec, Brackets("<", ">"));
    }

    template<uni::internal::derived_from_template<std::priority_queue> T>
    std::string operator()(T val) const {
        std::vector<typename T::value_type> vec;

        while(!val.empty()) vec.emplace_back(val.top()), val.pop();

        return dump_range_impl(vec, Brackets("<", ">"));
    }


    template<class T>
        requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::pair>
    std::string operator()(T&& val) const {
        std::stringstream res;
        res << "( " << dump(val.first) << ", " << dump(val.second) << " )";
        return res.str();
    }

    template<class T>
        requires uni::internal::derived_from_template<std::remove_cvref_t<T>, std::tuple>
    std::string operator()(T&& val) const {
        std::stringstream res;
        res << "( ";
        dump_tuple_impl<0>(val, res);
        res << " )";
        return res.str();
    }
};


struct dump_range {
    template<std::ranges::input_range T>
    std::string operator()(T&& val) const {
        return dump_range_impl(val);
    }
};


struct dump_loggable {
    template<uni::internal::loggable T>
    std::string operator()(T&& val) const {
        auto res = _debug(val);

        if constexpr(std::same_as<decltype(res), debug_t>) {
            return res;
        }
        else {
            return dump(res);
        }
    }
};


template<class T>
std::string dump(T&& val) {
    if constexpr(std::same_as<std::remove_cvref_t<T>, debug_t>) {
        // return "debug_t";
        return dump_debug_t(std::forward<T>(val));
    }

    if constexpr(std::invocable<dump_primitive_like, T>) {
        // return "primitive";
        return dump_primitive_like{}(std::forward<T>(val));
    }
    if constexpr(std::invocable<dump_loggable, T>) {
        // return "loggable";
        return dump_loggable{}(std::forward<T>(val));
    }
    if constexpr(std::invocable<dump_has_val, T>) {
        // return "has val";
        return dump_has_val{}(std::forward<T>(val));
    }

    if constexpr(std::invocable<dump_bitset, T>) {
        // return "bitset";
        return dump_bitset{}(std::forward<T>(val));
    }
    if constexpr(std::invocable<dump_iterator, T>) {
        // return "iterator";
        return dump_iterator{}(std::forward<T>(val));
    }

    if constexpr(std::invocable<dump_wrapper, T>) {
        // return "wrapper";
        return dump_wrapper{}(std::forward<T>(val));
    }

    if constexpr(std::invocable<dump_range, T>) {;
        // return "range";
        return dump_range{}(std::forward<T>(val));
    }

    return "== dump error ==";
}


template<class T> void debug(T&& val, const std::string& endl) {
    *cdebug << dump(val) << endl << std::flush;
}


constexpr std::string_view WHITESPACES = " \n\r\t\f\v";

std::string ltrim(const std::string &s)
{
    size_t start = s.find_first_not_of(WHITESPACES);
    return (start == std::string::npos) ? "" : s.substr(start);
}

std::string rtrim(const std::string &s)
{
    size_t end = s.find_last_not_of(WHITESPACES);
    return (end == std::string::npos) ? "" : s.substr(0, end + 1);
}

std::string trim(const std::string &s) {
    return rtrim(ltrim(s));
}

std::vector<std::string> split(const std::string& str) {
    static constexpr char SEPARATOR = ',';
    static constexpr char ESCAPE = '\\';
    static constexpr std::string_view QUOTATIONS = "\"\'";
    static constexpr std::string_view PARENTHESES = "()[]{}<>";
    static constexpr auto PARENTHESES_KINDS = std::ranges::size(PARENTHESES);
    static_assert(PARENTHESES_KINDS % 2 == 0);

    std::vector<std::string> res = { "" };

    bool quoted = false;
    std::array<int,(PARENTHESES_KINDS / 2)> enclosed = { 0 };

    for(auto itr = std::ranges::begin(str); itr != std::ranges::end(str); ++itr) {
        if(std::ranges::find(QUOTATIONS, *itr) != std::ranges::end(QUOTATIONS)) {
            if(itr == std::ranges::begin(str) or *std::ranges::prev(itr) != ESCAPE) {
                quoted ^= true;
            }
        }

        if(const auto found = std::ranges::find(PARENTHESES, *itr); found != std::ranges::end(PARENTHESES)) {
            if(not quoted) {
                auto& target = enclosed[std::ranges::distance(std::begin(PARENTHESES), found) / 2];
                target = std::max(0, target - static_cast<int>((std::ranges::distance(std::begin(PARENTHESES), found) % 2) * 2) + 1);

            }
        }

        if(
            not quoted
            and static_cast<std::size_t>(std::ranges::count(enclosed, 0)) == std::ranges::size(enclosed)
            and *itr == SEPARATOR
        ) {
            res.push_back("");
        }
        else {
            res.back() += *itr;
        }
    }

    for(auto&& v : res) v = trim(v);

    return res;
}

template<class Arg> void raw(std::nullptr_t, Arg&& arg) { *cdebug << std::forward<Arg>(arg) << std::flush; }
template<class Arg> void raw(Arg&& arg) { *cdebug << dump(std::forward<Arg>(arg)) << std::flush; }

void debug(const std::vector<std::string>, const size_t, const int, const std::string) { debug(nullptr, COLOR_INIT + "\n"); }


std::map<std::pair<std::string, int>, int> count;

template<class Head, class... Tail>
void debug(
    const std::vector<std::string> args, const size_t idx,
    const int line, const std::string path,
    Head&& H, Tail&&... T
) {
    if(idx == 0) {
        std::string file = path.substr(path.find_last_of("/") + 1);
        debug(nullptr, COLOR_LINE + file + " #" + std::to_string(line) + " (" + std::to_string(count[{ file, line }]++) + ")" + COLOR_INIT);
    }
    debug(nullptr, "\n - ");


    const std::string content = dump(H);
    const std::string type_name = get_type_name(std::forward<Head>(H));


    debug(nullptr, COLOR_IDENTIFIER + args[idx]  + COLOR_INIT + " : ");
    debug(nullptr, content);

    if(type_name.size() + content.size() >= 300) debug(nullptr, "\n   ");

    debug(nullptr, " " + type_name);

    debug(args, idx + 1, 0, path, std::forward<Tail>(T)...);
}


} // namespace debugger
#line 13 "template/debug.hpp"


#ifdef DEBUGGER_ENABLED


#define debug(...) debugger::debug(debugger::split(#__VA_ARGS__), 0, __LINE__, __FILE__, __VA_ARGS__)
#define debug_(...) do { const std::string file = __FILE__; debugger::raw(nullptr, debugger::COLOR_LINE + file.substr(file.find_last_of("/") + 1) + " #" + std::to_string(__LINE__) + debugger::COLOR_INIT + "  "); debugger::raw(__VA_ARGS__); debugger::raw(nullptr, debugger::COLOR_INIT + "\n"); } while(0);
#define DEBUG if constexpr(true)


#else


#define debug(...) ({ ; })
#define debug_(...) ({ ; })
#define DEBUG if constexpr(false)


#endif
#line 14 "graph/centroid_path_decomposition.hpp"

namespace uni {

// Thanks to: https://kazuma8128.hatenablog.com/entry/2018/07/16/010500#fn-96e76557
class centroid_path_decomposition {
    using size_type = internal::size_t;

  private:
    std::vector<std::vector<size_type>> graph;

  public:
    std::vector<size_type> in, out, size, head, parent;

  private:
    size_type _cur = 0;

    void _erase_parent(const size_type v, const size_type p) noexcept(NO_EXCEPT) {
        this->parent[v] = p;
        ITRR(nv, graph[v]) {
            if(nv == this->graph[v].back()) break;
            if(nv == p) std::swap(nv, this->graph[v].back());
            this->_erase_parent(nv, v);
        }
        this->graph[v].pop_back();
    }

    void _race_size(const size_type v) noexcept(NO_EXCEPT) {
        ITRR(nv, this->graph[v]) {
            this->_race_size(nv);
            this->size[v] += this->size[nv];
            if(this->size[nv] > this->size[this->graph[v].front()]) std::swap(nv, this->graph[v].front());
        }
    }

    void _race_path(const size_type v) noexcept(NO_EXCEPT) {
        this->in[v] = this->_cur++;
        ITR(nv, this->graph[v]) {
            this->head[nv] = (nv == this->graph[v].front() ? this->head[v] : nv);
            this->_race_path(nv);
        }
        this->out[v] = this->_cur;
    }

  public:
    template<class Graph>
    centroid_path_decomposition(const Graph& _graph, const size_type root = 0) noexcept(NO_EXCEPT)
      : graph(_graph.size()), in(_graph.size(), -1), out(_graph.size(), -1), size(_graph.size(), 1), head(_graph.size()), parent(_graph.size(), -1)
    {
        REP(v, _graph.size()) ITR(nv, _graph[v]) { this->graph[v].push_back(nv); }
        this->build(root);
    }

    void build(const size_type root = 0) noexcept(NO_EXCEPT) {
        ITR(v, this->graph[root]) this->_erase_parent(v, root);
        this->_race_size(root);
        this->head[root] = root;
        this->_race_path(root);
    }

    size_type id(const size_type v) noexcept(NO_EXCEPT) { return this->in[v]; }

    size_type lca(size_type u, size_type v) const noexcept(NO_EXCEPT) {
        while(true) {
            if(this->in[u] > this->in[v]) std::swap(u, v);
            if(this->head[u] == this->head[v]) return u;
            v = this->parent[this->head[v]];
        }
    }

    template<class F>
    void edges_on_path(size_type u, size_type v, F&& f) noexcept(NO_EXCEPT) {
        while(true) {
            if(this->in[u] > this->in[v]) std::swap(u, v);
            if(this->head[u] != this->head[v]) {
                f(this->in[this->head[v]] - 1, this->in[v]);
                v = this->parent[this->head[v]];
            } else {
                if(u != v) f(this->in[u], this->in[v]);
                break;
            }
        }
    }

    template<class F>
    void nodes_on_path(size_type u, size_type v, F&& f) noexcept(NO_EXCEPT) {
        while (true) {
            if (this->in[u] > this->in[v]) std::swap(u, v);
            f(std::max(this->in[this->head[v]], this->in[u]), this->in[v]);
            if (this->head[u] != this->head[v])
                v = this->parent[this->head[v]];
            else {
                break;
            }
        }
    }

    template<class F>
    void subtree(const size_type v, F&& f) noexcept(NO_EXCEPT) { f(this->in[v], this->out[v]); }
};


} // namespace uni

Back to top page