#pragma once
#include "../../util/traits/ds/lib.hpp"
namespace tifa_libs {
template <tp2_ds_c pointer, class F>
requires requires(pointer p, F&& f) { f(p); }
CEXP void pre_order(pointer p, F&& f) NE {
if (p) f(p), pre_order(p->ch[0], std::forward<F>(f)), pre_order(p->ch[1], std::forward<F>(f));
}
template <tp2_ds_c pointer, class F>
requires requires(pointer p, F f) { f(p); }
CEXP void in_order(pointer p, F&& f) NE {
if (p) in_order(p->ch[0], std::forward<F>(f)), f(p), in_order(p->ch[1], std::forward<F>(f));
}
template <tp2_ds_c pointer, class F>
requires requires(pointer p, F f) { f(p); }
CEXP void post_order(pointer p, F&& f) NE {
if (p) post_order(p->ch[0], std::forward<F>(f)), post_order(p->ch[1], std::forward<F>(f)), f(p);
}
template <tp_ds_c pointer, class F>
requires requires(pointer p, u32 level, F f) { f(p, level); }
CEXP void level_order(pointer p, F&& f) NE {
if (!p) return;
u32 level = 0;
std::queue<pointer> q({p});
while (!q.empty()) {
flt_ (u32, i, 0, (u32)q.size()) {
auto now = q.front();
q.pop(), f(now, level);
for (auto&& s : now->ch) q.push(s);
}
++level;
}
}
template <tp_ds_c pointer, class Alloc>
CEXP void dealloc_subtree(pointer p, Alloc& alloc) NE {
if (!p) return;
for (auto&& s : p->ch) dealloc_subtree(s, alloc);
alloc.deallocate(p, 1);
}
template <tp_ds_c pointer>
CEXP pointer most(pointer p, bool dir) NE {
if (!p) return nullptr;
while (p->ch[dir]) p = p->ch[dir];
return p;
}
template <tp2_ds_c pointer>
CEXP auto leftmost(pointer p) NE { return most(p, 0); }
template <tp2_ds_c pointer>
CEXP auto rightmost(pointer p) NE { return most(p, 1); }
} // namespace tifa_libs
#line 2 "src/ds/bt_trv/lib.hpp"
#line 2 "src/util/traits/ds/lib.hpp"
// clang-format off
#line 2 "src/util/alias/num/lib.hpp"
#line 2 "src/util/util/lib.hpp"
// https://github.com/Tiphereth-A/CP-lib
#include <bits/extc++.h>
// clang-format off
namespace tifa_libs {
#define CEXP constexpr
#define CEXPE constexpr explicit
#define CR const&
#define CP const*
#define PC *const
#define CPC const*const
#define TPN typename
#define NE noexcept
#define CNE const noexcept
#define ND [[nodiscard]]
#define cT_(...) std::conditional_t<sizeof(__VA_ARGS__) <= sizeof(size_t) * 2, __VA_ARGS__, __VA_ARGS__ CR>
// NOLINTNEXTLINE(misc-const-correctness)
#define flt_(T, i, l, r, ...) for (T i = (l), i##e = (r)__VA_OPT__(, ) __VA_ARGS__; i < i##e; ++i)
#define retif_(cond, if_true, ...) if cond return if_true __VA_OPT__(; else return __VA_ARGS__)
#ifdef ONLINE_JUDGE
#undef assert
#define assert(x) 42
#endif
using namespace std::ranges;
using namespace std::literals;
template <class T>
CEXP T abs(T x) NE { retif_((x < 0), -x, x); }
} // namespace tifa_libs
// clang-format on
#line 4 "src/util/alias/num/lib.hpp"
// clang-format off
namespace tifa_libs {
#define mk0_(w, t) using w = t; using c##w = const t
#define mk_(w, t) mk0_(w, t); CEXP w operator""_##w(unsigned long long x) NE { return (w)x; }
mk_(i8, int8_t) mk_(u8, uint8_t) mk_(i16, int16_t) mk_(u16, uint16_t) mk_(i32, int32_t) mk_(u32, uint32_t) mk_(i64, int64_t) mk_(u64, uint64_t) mk_(isz, ssize_t) mk_(usz, size_t) mk_(chr, char) mk_(schr, signed char) mk_(uchr, unsigned char) mk_(sint, signed) mk_(uint, unsigned);
mk0_(i128, __int128_t); mk0_(u128, __uint128_t); mk0_(f32, float); mk0_(f64, double); mk0_(f128, long double);
#undef mk0_
#undef mk_
} // namespace tifa_libs
// clang-format on
#line 4 "src/util/traits/ds/lib.hpp"
namespace tifa_libs {
// tree pointer (for DS)
template <class P> concept tp_ds_c = requires(P p) { p->ch; std::is_array_v<decltype(p->ch)>; std::rank_v<decltype(p->ch)> == 1; };
// binary tree pointer (for DS)
template <class P> concept tp2_ds_c = tp_ds_c<P> && std::extent_v<decltype(std::declval<P>()->ch)> == 2;
template <class T> concept dsu_c = requires(T dsu, u32 x, u32 y) { {dsu.find(x)} -> std::same_as<i32>; {dsu.size()} -> std::same_as<u32>; {dsu.size(x)} -> std::same_as<u32>; {dsu.same(x, y)} -> std::same_as<bool>; {dsu.merge(x, y)} -> std::same_as<bool>; };
} // namespace tifa_libs
// clang-format on
#line 4 "src/ds/bt_trv/lib.hpp"
namespace tifa_libs {
template <tp2_ds_c pointer, class F>
requires requires(pointer p, F&& f) { f(p); }
CEXP void pre_order(pointer p, F&& f) NE {
if (p) f(p), pre_order(p->ch[0], std::forward<F>(f)), pre_order(p->ch[1], std::forward<F>(f));
}
template <tp2_ds_c pointer, class F>
requires requires(pointer p, F f) { f(p); }
CEXP void in_order(pointer p, F&& f) NE {
if (p) in_order(p->ch[0], std::forward<F>(f)), f(p), in_order(p->ch[1], std::forward<F>(f));
}
template <tp2_ds_c pointer, class F>
requires requires(pointer p, F f) { f(p); }
CEXP void post_order(pointer p, F&& f) NE {
if (p) post_order(p->ch[0], std::forward<F>(f)), post_order(p->ch[1], std::forward<F>(f)), f(p);
}
template <tp_ds_c pointer, class F>
requires requires(pointer p, u32 level, F f) { f(p, level); }
CEXP void level_order(pointer p, F&& f) NE {
if (!p) return;
u32 level = 0;
std::queue<pointer> q({p});
while (!q.empty()) {
flt_ (u32, i, 0, (u32)q.size()) {
auto now = q.front();
q.pop(), f(now, level);
for (auto&& s : now->ch) q.push(s);
}
++level;
}
}
template <tp_ds_c pointer, class Alloc>
CEXP void dealloc_subtree(pointer p, Alloc& alloc) NE {
if (!p) return;
for (auto&& s : p->ch) dealloc_subtree(s, alloc);
alloc.deallocate(p, 1);
}
template <tp_ds_c pointer>
CEXP pointer most(pointer p, bool dir) NE {
if (!p) return nullptr;
while (p->ch[dir]) p = p->ch[dir];
return p;
}
template <tp2_ds_c pointer>
CEXP auto leftmost(pointer p) NE { return most(p, 0); }
template <tp2_ds_c pointer>
CEXP auto rightmost(pointer p) NE { return most(p, 1); }
} // namespace tifa_libs
src/ds/bt_trv/lib.hpp