パス和取得ができる Link Cut Tree
(library/tree/link_cut_tree_path_foldable.hpp)

View this file on GitHub
Last update: 2022-06-23 03:06:22+09:00
Include: #include "library/tree/link_cut_tree_path_foldable.hpp"

パス和取得ができる Link Cut Tree

サポートする関数

全てstatic 関数として各種操作をサポートされる．

static void init_pool(int capacity)

使用前に必ず呼ぶこと． capacity には使用するノード数を与える．
static node_pointer_type make_node(const value_type &val)

値 val を持つノードを作成して返す．
static std::vector<node_pointer_type> make_node(const std::vector<value_type> &vals)

vals の各要素 val に対して make_node(val) を呼び，その結果を std::vector<node_pointer_type> に元の順番通りに格納して返す．
static node_pointer_type expose(node_pointer_type node)

node から根までを heavy path で結ぶ．node の子への link は全て light edge となり，heavy path を管理する splay 木において node は根となる．返り値は通常の用途において使用しない (と思う)．expose 自体を外から使うこと自体が少なそう．
static void link(node_pointer_type ch, node_pointer_type par

ch が属する木で ch を根にした (evert) 後，par の子に ch を追加する．操作前に ch と par が連結であってはならない．
static void cut(node_pointer_type ch)

ch と ch の親の間の辺を削除する．操作前に ch が根であってはならない．
static void cut(node_pointer_type u, node_pointer_type v)

u と v の間の辺を削除する．操作前に u と v を直接結ぶ辺が存在しなければならない．
static void evert(node_pointer_type u)

u が属する木の根を u に変更する．
static bool is_connected(node_pointer_type u, node_pointer_type v)

u と v が連結なら true，そうでなければ false を返す．
static node_pointer_type lca(node_pointer_type u, node_pointer_type v)

u と v の Lowest Common Ancestor を返す．u と v が異なる木に属する場合は，nullptr を返す．u および v が属している木の根 r を指定するためには先に evert(r) を呼ぶこと (詳しくは lca のテストファイルを参照)．
static value_type prod_from_root(node_pointer_type u)

u が属する木の根から u までのパス上の頂点を順番に op で畳込んだ結果を返す．
static value_type prod(node_pointer_type u, node_pointer_type v)

u から v へのパス上の頂点を順番に op で畳込んだ結果を返す．操作前の時点で u と v は連結でなければならない．
static value_type get(node_pointer_type u)

u に書かれた値を返す．
static void set(node_pointer_type u, const value_type &val)

u に書かれた値を val に更新する
template <typename Fun> static void apply(node_pointer_type u, Fun&& f)

u に書かれた値 val を f(val) に更新する．即ち，Fun は value_type -> value_type の関数型を想定している．
static std::vector<node_pointer_type> path_from_root(node_pointer_type u)

u が属する木の根から u までのパスを返す．
static std::optional<std::vector<node_pointer_type>> path(node_pointer_type u, node_pointer_type v)

u から v までのパスを返す．操作前に u と v が連結である必要がある．

注意点

evert を呼び出した後でも，その他の関数によって根が再び別の頂点に変更される可能性がある．具体的には，以下の関数では根の変更が暗黙的に行われる．

link

この操作では2つの連結成分が merge されるので，根は par 側の根に統一される．
cut(node_pointer_type ch)

操作後の ch 側の木の根は ch である．親側の根は変化しない．
cut(node_pointer_type u, node_pointer_type v)

操作後の u 側の木の根は u に，v 側の木の根は v となる．
evert(node_pointer_type u)

操作後に u が根となる．
prod(node_pointer_type u, node_pointer_type v)

操作後に u が根となる．
path(node_pointer_type u, node_pointer_type v)

操作後に u が根となる．

使い方

#include "library/tree/link_cut_tree_path_foldable.hpp"

int op(int x, int y) { return x + y; } // モノイドの二項演算
int e() { return 0; }                  // モノイドの単位元
int toggle(int x) { return x; }        // モノイドが非可換な場合は，逆順で和を取ったものを同時に計算してここで swap する

using DynamicTree = suisen::LinkCutTreePathFoldable<int, op, e, toggle>;

int main() {
    const int n = 5;
    
    DynamicTree::init_pool(n); // 使用するノードの個数を予め確保

    std::vector<int> init_values { 1, 2, 3, 4, 5 };

    std::vector<DynamicTree::node_pointer_type> nodes = DynamicTree::make_nodes(init_values);

    /**
     * ノードを [添字(値)] と表記
     * 
     * [0(1)]   [1(2)]   [2(3)]   [3(4)]   [4(5)]
     */
    
    // nodes[0] と nodes[1] の間に辺を張る (操作前に非連結である必要がある)
    DynamicTree::link(nodes[0], nodes[1]);
    /**
     * [0(1)]---[1(2)]   [2(3)]   [3(4)]   [4(5)]
     */
    DynamicTree::link(nodes[1], nodes[4]);
    /**
     * [0(1)]---[1(2)]---[4(5)]   [2(3)]   [3(4)]
     */
    DynamicTree::link(nodes[1], nodes[3]);
    /**
     * [0(1)]---[1(2)]---[4(5)]   [2(3)]
     *            |
     *          [3(4)]
     */

    // nodes[3] から nodes[4] までのパス上の値を二項演算 op で畳込む
    int sum = DynamicTree::prod(nodes[3], nodes[4]); // 4 + 2 + 5

    // nodes[3] と nodes[4] の間の辺を切る (操作前に直接結ぶ辺が存在する必要がある)
    DynamicTree::cut(nodes[1], nodes[4]);
    /**
     * [0(1)]---[1(2)]   [4(5)]   [2(3)]
     *            |
     *          [3(4)]
     */
    DynamicTree::link(nodes[0], nodes[4]);
    /**
     * [4(5)]---[0(1)]---[1(2)]     [2(3)]
     *                     |
     *                   [3(4)]
     */
    DynamicTree::link(nodes[0], nodes[2]);
    /**
     * [4(5)]---[0(1)]---[1(2)]
     *            |        |
     *          [2(3)]   [3(4)]
     */
    
    // nodes[1] を，nodes[1] が属する木の根にする (以降の操作で根は勝手に変更される可能性があるので，毎回evertを呼ぶ)
    DynamicTree::evert(nodes[1]);
    /**
     * [1(2)]
     *  |  |
     *  |  +------+
     *  |         |
     * [0(1)]  [3(4)]
     *  |  |
     *  |  +------+
     *  |         |
     * [4(5)]  [2(3)]
     */

    // nodes[2] と nodes[4] の lca を返す．今は nodes[1] が根なので，lca は nodes[0];
    DynamicTree::node_pointer_type a = DynamicTree::lca(nodes[0], nodes[3]);
    return 0;
}

Depends on

Verified with

Code

#ifndef SUISEN_LINK_CUT_TREE
#define SUISEN_LINK_CUT_TREE

#include "library/tree/link_cut_tree_base.hpp"

namespace suisen {
    namespace internal::link_cut_tree {
        template <typename T, T(*op)(T, T), T(*e)(), T(*toggle)(T)>
        struct PathFoldableSplayTreeNode : public SplayTreeNodeBase<T, PathFoldableSplayTreeNode<T, op, e, toggle>> {
            using base_node_type = SplayTreeNodeBase<T, PathFoldableSplayTreeNode<T, op, e, toggle>>;
            
            template <typename, typename>
            friend struct SplayTreeNodeBase;
            template <typename, typename>
            friend struct LinkCutTreeBase;
            template <typename T2, T2(*)(T2, T2), T2(*)(), T2(*)(T2)>
            friend struct LinkCutTreePathFoldable;

            using value_type = typename base_node_type::value_type;
            using node_type = typename base_node_type::node_type;
            using node_pointer_type = typename base_node_type::node_pointer_type;

            explicit PathFoldableSplayTreeNode(const value_type& val = e()) : base_node_type(val), _sum(val) {}

        protected:
            value_type _sum;

            static value_type sum(node_pointer_type node) {
                return node ? node->_sum : e();
            }
            static void update(node_pointer_type node) {
                base_node_type::update(node);
                node->_sum = op(op(node_type::sum(node_type::child(node, 0)), node_type::value(node)), node_type::sum(node_type::child(node, 1)));
            }

            static void reverse_all(node_pointer_type node) {
                if (not node) return;
                base_node_type::reverse_all(node);
                node->_sum = toggle(node->_sum);
            }
        };

        template <typename T, T(*op)(T, T), T(*e)(), T(*toggle)(T)>
        struct LinkCutTreePathFoldable : public LinkCutTreeBase<PathFoldableSplayTreeNode<T, op, e, toggle>, LinkCutTreePathFoldable<T, op, e, toggle>> {
            using base_type = LinkCutTreeBase<PathFoldableSplayTreeNode<T, op, e, toggle>, LinkCutTreePathFoldable<T, op, e, toggle>>;
            using node_type = PathFoldableSplayTreeNode<T, op, e, toggle>;
            using node_pointer_type = typename node_type::node_pointer_type;
            using value_type = typename node_type::value_type;

            static value_type prod_from_root(node_pointer_type u) {
                base_type::expose(u);
                return node_type::sum(u);
            }
            static value_type prod(node_pointer_type u, node_pointer_type v) {
                base_type::evert(u);
                base_type::expose(v);
                // check connectivity
                if (not (u == v or node_type::parent(u))) assert(false);
                return node_type::sum(v);
            }
        };
    } // namespace internal::link_cut_tree
    
    using internal::link_cut_tree::LinkCutTreePathFoldable;
} // namespace suisen

#endif // SUISEN_LINK_CUT_TREE

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



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



#include <cassert>
#include <optional>
#include <utility>
#include <vector>

#line 1 "library/util/object_pool.hpp"



#include <deque>
#line 6 "library/util/object_pool.hpp"

namespace suisen {
    template <typename T, bool auto_extend = false>
    struct ObjectPool {
        using value_type = T;
        using value_pointer_type = T*;

        template <typename U>
        using container_type = std::conditional_t<auto_extend, std::deque<U>, std::vector<U>>;

        container_type<value_type> pool;
        container_type<value_pointer_type> stock;
        decltype(stock.begin()) it;

        ObjectPool() : ObjectPool(0) {}
        ObjectPool(int siz) : pool(siz), stock(siz) {
            clear();
        }

        int capacity() const { return pool.size(); }
        int size() const { return it - stock.begin(); }

        value_pointer_type alloc() {
            if constexpr (auto_extend) ensure();
            return *it++;
        }

        void free(value_pointer_type t) {
            *--it = t;
        }

        void clear() {
            int siz = pool.size();
            it = stock.begin();
            for (int i = 0; i < siz; i++) stock[i] = &pool[i];
        }

        void ensure() {
            if (it != stock.end()) return;
            int siz = stock.size();
            for (int i = siz; i <= siz * 2; ++i) {
                stock.push_back(&pool.emplace_back());
            }
            it = stock.begin() + siz;
        }
    };
} // namespace suisen


#line 10 "library/tree/link_cut_tree_base.hpp"

namespace suisen::internal::link_cut_tree {
    template <typename T, typename Derived>
    struct SplayTreeNodeBase {
        friend Derived;
        template <typename, typename>
        friend struct LinkCutTreeBase;

        using value_type = T;
        using node_type = Derived;
        using node_pointer_type = node_type*;

        explicit SplayTreeNodeBase(const value_type& val = value_type{}) : _val(val) {}

    protected:
        node_pointer_type _p = nullptr;
        node_pointer_type _ch[2]{ nullptr, nullptr };

        int _siz = 1;
        value_type _val;

        bool _rev = false;
        
        static bool is_root(node_pointer_type node) {
            return not node->_p or (node->_p->_ch[0] != node and node->_p->_ch[1] != node);
        }
        static node_pointer_type& parent(node_pointer_type node) {
            return node->_p;
        }
        static node_pointer_type& child(node_pointer_type node, int ch_idx) {
            return node->_ch[ch_idx];
        }
        static int size(node_pointer_type node) {
            return node ? node->_siz : 0;
        }
        static const value_type& value(node_pointer_type node) {
            return node->_val;
        }
        static void set_value(node_pointer_type node, const value_type &new_val) {
            node->_val = new_val;
        }
        static void update(node_pointer_type node) {
            node->_siz = 1 + node_type::size(node->_ch[0]) + node_type::size(node->_ch[1]);
        }

        static void reverse_all(node_pointer_type node) {
            if (not node) return;
            node->_rev ^= true;
            std::swap(node->_ch[0], node->_ch[1]);
        }

        static void push(node_pointer_type node) {
            if (std::exchange(node->_rev, false)) {
                node_type::reverse_all(node->_ch[0]);
                node_type::reverse_all(node->_ch[1]);
            }
        }

        static void rot(node_pointer_type node, int ch_idx) {
            assert(node->_ch[ch_idx]);

            node_pointer_type rt = node->_ch[ch_idx];
            if (not node_type::is_root(node)) node->_p->_ch[node->_p->_ch[1] == node] = rt;

            if ((node->_ch[ch_idx] = rt->_ch[ch_idx ^ 1])) node->_ch[ch_idx]->_p = node;

            rt->_ch[ch_idx ^ 1] = node;
            rt->_p = std::exchange(node->_p, rt);

            node_type::update(node), node_type::update(rt);
        }

        static void splay(node_pointer_type node) {
            node_type::push(node);
            while (not node_type::is_root(node)) {
                node_pointer_type p = node->_p;
                if (node_type::is_root(p)) {
                    node_type::push(p), node_type::push(node);
                    node_type::rot(p, p->_ch[1] == node);
                } else {
                    node_pointer_type pp = p->_p;
                    node_type::push(pp), node_type::push(p), node_type::push(node);
                    const int idx_pp = pp->_ch[1] == p, idx_p = p->_ch[1] == node;
                    if (idx_p == idx_pp) {
                        node_type::rot(pp, idx_pp), node_type::rot(p, idx_p);
                    } else {
                        node_type::rot(p, idx_p), node_type::rot(pp, idx_pp);
                    }
                }
            }
        }
    };

    template <typename NodeType, typename Derived>
    struct LinkCutTreeBase {
        using derived_tree_type = Derived;

        using node_type = typename NodeType::node_type;
        using node_pointer_type = typename NodeType::node_pointer_type;
        using value_type = typename NodeType::value_type;

        LinkCutTreeBase() = delete;

        static void init_pool(int capacity) {
            _pool = ObjectPool<node_type>(capacity);
        }

        template <typename ...Args>
        static node_pointer_type make_node(Args&&...args) {
            return &(*_pool.alloc() = node_type(std::forward<Args>(args)...));
        }
        static std::vector<node_pointer_type> make_nodes(const std::vector<value_type>& vals) {
            std::vector<node_pointer_type> nodes;
            nodes.reserve(vals.size());
            for (const auto& val : vals) nodes.push_back(make_node(val));
            return nodes;
        }

        static node_pointer_type expose(node_pointer_type node) {
            assert(node);
            node_pointer_type rch = nullptr;
            for (node_pointer_type cur = node; cur; cur = node_type::parent(cur)) {
                node_type::splay(cur);
                node_type::child(cur, 1) = std::exchange(rch, cur);
                node_type::update(cur);
            }
            node_type::splay(node);
            return rch;
        }

        static void link(node_pointer_type ch, node_pointer_type par) {
            derived_tree_type::evert(ch), derived_tree_type::expose(par);
            // check un-connectivity
            if (ch == par or node_type::parent(ch)) assert(false);
            node_type::child(par, 1) = ch;
            node_type::parent(ch) = par;
            node_type::update(par);
        }

        static void cut(node_pointer_type ch) {
            derived_tree_type::expose(ch);
            node_pointer_type par = node_type::child(ch, 0);
            assert(par);
            node_type::parent(par) = node_type::child(ch, 0) = nullptr;
            node_type::update(ch);
        }
        static void cut(node_pointer_type u, node_pointer_type v) {
            derived_tree_type::evert(u);
            derived_tree_type::expose(v);
            // check connectivity
            if (node_type::child(v, 0) != u) assert(false);
            node_type::parent(u) = node_type::child(v, 0) = nullptr;
            node_type::update(v);
        }

        static void evert(node_pointer_type u) {
            derived_tree_type::expose(u);
            node_type::reverse_all(u);
            node_type::push(u);
        }

        static bool is_connected(node_pointer_type u, node_pointer_type v) {
            derived_tree_type::expose(u), derived_tree_type::expose(v);
            return u == v or node_type::parent(u);
        }

        static node_pointer_type lca(node_pointer_type u, node_pointer_type v) {
            derived_tree_type::expose(u);
            node_pointer_type a = derived_tree_type::expose(v);
            return u == v or node_type::parent(u) ? a : nullptr;
        }

        static value_type get(node_pointer_type u) {
            // expose(u);
            return node_type::value(u);
        }
        static void set(node_pointer_type u, const value_type& val) {
            derived_tree_type::update_value(u, [&val](const value_type&) { return val; });
        }
        template <typename Fun>
        static void update_value(node_pointer_type u, Fun&& f) {
            derived_tree_type::expose(u);
            node_type::set_value(u, f(node_type::value(u)));
            node_type::update(u);
        }

        static std::vector<node_pointer_type> path_from_root(node_pointer_type u) {
            std::vector<node_pointer_type> res;
            derived_tree_type::expose(u);
            auto dfs = [&](auto dfs, node_pointer_type cur) -> void {
                node_type::push(cur);
                if (node_type::child(cur, 0)) dfs(dfs, node_type::child(cur, 0));
                res.push_back(cur);
                if (node_type::child(cur, 1)) dfs(dfs, node_type::child(cur, 1));
            };
            dfs(dfs, u);
            return res;
        }
        static std::optional<std::vector<node_pointer_type>> path(node_pointer_type u, node_pointer_type v) {
            derived_tree_type::evert(u);
            derived_tree_type::expose(v);
            if (u == v or node_type::parent(u)) return derived_tree_type::path_from_root(v);
            return std::nullopt;
        }
    
    private:
        static inline ObjectPool<node_type> _pool{};
    };
} // namespace suisen


#line 5 "library/tree/link_cut_tree_path_foldable.hpp"

namespace suisen {
    namespace internal::link_cut_tree {
        template <typename T, T(*op)(T, T), T(*e)(), T(*toggle)(T)>
        struct PathFoldableSplayTreeNode : public SplayTreeNodeBase<T, PathFoldableSplayTreeNode<T, op, e, toggle>> {
            using base_node_type = SplayTreeNodeBase<T, PathFoldableSplayTreeNode<T, op, e, toggle>>;
            
            template <typename, typename>
            friend struct SplayTreeNodeBase;
            template <typename, typename>
            friend struct LinkCutTreeBase;
            template <typename T2, T2(*)(T2, T2), T2(*)(), T2(*)(T2)>
            friend struct LinkCutTreePathFoldable;

            using value_type = typename base_node_type::value_type;
            using node_type = typename base_node_type::node_type;
            using node_pointer_type = typename base_node_type::node_pointer_type;

            explicit PathFoldableSplayTreeNode(const value_type& val = e()) : base_node_type(val), _sum(val) {}

        protected:
            value_type _sum;

            static value_type sum(node_pointer_type node) {
                return node ? node->_sum : e();
            }
            static void update(node_pointer_type node) {
                base_node_type::update(node);
                node->_sum = op(op(node_type::sum(node_type::child(node, 0)), node_type::value(node)), node_type::sum(node_type::child(node, 1)));
            }

            static void reverse_all(node_pointer_type node) {
                if (not node) return;
                base_node_type::reverse_all(node);
                node->_sum = toggle(node->_sum);
            }
        };

        template <typename T, T(*op)(T, T), T(*e)(), T(*toggle)(T)>
        struct LinkCutTreePathFoldable : public LinkCutTreeBase<PathFoldableSplayTreeNode<T, op, e, toggle>, LinkCutTreePathFoldable<T, op, e, toggle>> {
            using base_type = LinkCutTreeBase<PathFoldableSplayTreeNode<T, op, e, toggle>, LinkCutTreePathFoldable<T, op, e, toggle>>;
            using node_type = PathFoldableSplayTreeNode<T, op, e, toggle>;
            using node_pointer_type = typename node_type::node_pointer_type;
            using value_type = typename node_type::value_type;

            static value_type prod_from_root(node_pointer_type u) {
                base_type::expose(u);
                return node_type::sum(u);
            }
            static value_type prod(node_pointer_type u, node_pointer_type v) {
                base_type::evert(u);
                base_type::expose(v);
                // check connectivity
                if (not (u == v or node_type::parent(u))) assert(false);
                return node_type::sum(v);
            }
        };
    } // namespace internal::link_cut_tree
    
    using internal::link_cut_tree::LinkCutTreePathFoldable;
} // namespace suisen

パス和取得ができる Link Cut Tree (library/tree/link_cut_tree_path_foldable.hpp)

パス和取得ができる Link Cut Tree

サポートする関数

注意点

使い方

Depends on

Verified with

Code

パス和取得ができる Link Cut Tree
(library/tree/link_cut_tree_path_foldable.hpp)