Link-Cut Tree (data_structure/link_cut_tree.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-05-10 13:38:02+09:00
• Include: #include "data_structure/link_cut_tree.hpp"

動的な木に対する操作（辺の追加・削除、パス上の集約値取得など）を高速に行うことができるデータ構造です。

テンプレートパラメータ:

• T: 要素の型。
• op: 二項演算 (モノイド)。T op(T, T) の形式である必要があります。
• e: モノイドの単位元を返す関数。T e() の形式である必要があります。

使い方

add

void add(T x)

説明

新しいノードに値 x を追加します。ノードのインデックスは追加された順に0から割り当てられます。

• x: 追加する要素の値。

計算量

$O(1)$

link

void link(int u, int v)

説明

ノード u とノード v の間に辺を追加し、2つの木を連結します。u は根である必要があります。

• u: 辺を追加するノードのインデックス (0-indexed)。根である必要がある。
• v: 辺を追加するノードのインデックス (0-indexed)。

制約

• u と v は異なる木に属している必要があります。
• u はその木において根である必要があります。

計算量

$O(\log N)$ (amortized)

expose

void expose(nptr& ptr)

説明

ノード ptr をその属する木の根からの優先パスの最上部に持ち上げます。これにより、根から ptr までのパスがSplay Treeとして表現されます。

• ptr: exposeするノードへのポインタ。

計算量

$O(\log N)$ (amortized)

evert

void evert(nptr ptr)

説明

ノード ptr をその属する木の新しい根とします。

• ptr: 新しい根とするノードへのポインタ。

計算量

$O(\log N)$ (amortized)

cut

void cut(int U, int V)

説明

ノード U とノード V の間の辺を削除します。U は V の親である必要があります。

• U: 辺を削除するノードのインデックス (0-indexed)。V の親である必要がある。
• V: 辺を削除するノードのインデックス (0-indexed)。

制約

• U と V は同じ木に属している必要があります。
• U は V の親である必要があります。

計算量

$O(\log N)$ (amortized)

set

void set(int U, T x)

説明

ノード U の値を x に更新します。

• U: 値を更新するノードのインデックス (0-indexed)。
• x: 更新後の値。

計算量

$O(\log N)$ (amortized)

operator[]

T operator[](int U)

説明

ノード U の値を返します。

• U: 値を取得するノードのインデックス (0-indexed)。
• 戻り値: ノード U の値。

計算量

$O(\log N)$ (amortized)

operator()

T operator()(int U, int V)

説明

ノード U とノード V の間のパス上の値の集約結果を返します。U を根とする木において、V までのパスの集約値を取得します。

• U: パスの開始ノードのインデックス (0-indexed)。根である必要がある。
• V: パスの終了ノードのインデックス (0-indexed)。
• 戻り値: パス上の値の集約結果。

制約

• U と V は同じ木に属している必要があります。
• U はその木において根である必要があります。

計算量

$O(\log N)$ (amortized)

Depends on

• data_structure/splay_tree.hpp

Verified with

• test/dynamic_tree_vertex_add_path_sum.test.cpp
• test/dynamic_tree_vertex_set_path_composite.test.cpp
• test/lca.test.cpp

Code

#pragma once
#include <cstdint>
#include <data_structure/splay_tree.hpp>
#include <vector>

template <typename T, auto op, auto e>
struct LinkCutTree : public SplayTree<T, op, e> {
    using Splay = SplayTree<T, op, e>;
    using nptr = Splay::nptr;
    std::vector<nptr> node;

    LinkCutTree() {}
    LinkCutTree(int n) {
        for (int i = 0; i < n; i++) {
            add(e());
        }
    }
    LinkCutTree(const std::vector<std::vector<int>>& g) : LinkCutTree(g, std::vector<T>(g.size(), e())) {}
    LinkCutTree(const std::vector<std::vector<int>>& g, const std::vector<T>& v) {
        for (uint32_t i = 0, siz = v.size(); i < siz; ++i) {
            add(v[i]);
        }
        for (int u = 0, siz = v.size(); u < siz; ++u) {
            for (int v : g[u]) {
                if (u > v) continue;
                link(u, v);
            }
        }
    }

    void add(T x) {
        node.emplace_back(new Splay::node{x, static_cast<int>(node.size())});
    }

    int expose(nptr& ptr) {
        nptr last = ptr;
        while (true) {
            Splay::splay(ptr);
            ptr->right = nullptr;
            Splay::update(ptr);
            if (!ptr->parent) {
                return last->idx;
            }
            last = ptr->parent;
            Splay::splay(ptr->parent);
            ptr->parent->right = ptr;
            Splay::update(ptr->parent);
        }
    }

    void evert(nptr ptr) {
        expose(ptr);
        Splay::toggle(ptr);
    }

    void link(int U, int V) {
        nptr u = node[U];
        nptr v = node[V];
        evert(v);
        v->parent = u;
    }

    void cut(int U, int V) {
        nptr u = node[U];
        nptr v = node[V];
        evert(u);
        expose(v);
        v->left->parent = nullptr;
        v->left = nullptr;
        Splay::update(v);
    }

    void set(int U, T x) {
        nptr u = node[U];
        expose(u);
        u->v = x;
        Splay::update(u);
    }

    T operator[](int U) {
        nptr u = node[U];
        expose(u);
        return u->v;
    }

    T operator()(int U, int V) {
        nptr u = node[U];
        nptr v = node[V];
        evert(u);
        expose(v);
        return v->p;
    }

    int lca(int U, int V) {
        nptr u = node[U];
        nptr v = node[V];
        expose(u);
        return expose(v);
    }
};

#line 2 "data_structure/link_cut_tree.hpp"
#include <cstdint>
#include <data_structure/splay_tree.hpp>
#include <vector>

template <typename T, auto op, auto e>
struct LinkCutTree : public SplayTree<T, op, e> {
    using Splay = SplayTree<T, op, e>;
    using nptr = Splay::nptr;
    std::vector<nptr> node;

    LinkCutTree() {}
    LinkCutTree(int n) {
        for (int i = 0; i < n; i++) {
            add(e());
        }
    }
    LinkCutTree(const std::vector<std::vector<int>>& g) : LinkCutTree(g, std::vector<T>(g.size(), e())) {}
    LinkCutTree(const std::vector<std::vector<int>>& g, const std::vector<T>& v) {
        for (uint32_t i = 0, siz = v.size(); i < siz; ++i) {
            add(v[i]);
        }
        for (int u = 0, siz = v.size(); u < siz; ++u) {
            for (int v : g[u]) {
                if (u > v) continue;
                link(u, v);
            }
        }
    }

    void add(T x) {
        node.emplace_back(new Splay::node{x, static_cast<int>(node.size())});
    }

    int expose(nptr& ptr) {
        nptr last = ptr;
        while (true) {
            Splay::splay(ptr);
            ptr->right = nullptr;
            Splay::update(ptr);
            if (!ptr->parent) {
                return last->idx;
            }
            last = ptr->parent;
            Splay::splay(ptr->parent);
            ptr->parent->right = ptr;
            Splay::update(ptr->parent);
        }
    }

    void evert(nptr ptr) {
        expose(ptr);
        Splay::toggle(ptr);
    }

    void link(int U, int V) {
        nptr u = node[U];
        nptr v = node[V];
        evert(v);
        v->parent = u;
    }

    void cut(int U, int V) {
        nptr u = node[U];
        nptr v = node[V];
        evert(u);
        expose(v);
        v->left->parent = nullptr;
        v->left = nullptr;
        Splay::update(v);
    }

    void set(int U, T x) {
        nptr u = node[U];
        expose(u);
        u->v = x;
        Splay::update(u);
    }

    T operator[](int U) {
        nptr u = node[U];
        expose(u);
        return u->v;
    }

    T operator()(int U, int V) {
        nptr u = node[U];
        nptr v = node[V];
        evert(u);
        expose(v);
        return v->p;
    }

    int lca(int U, int V) {
        nptr u = node[U];
        nptr v = node[V];
        expose(u);
        return expose(v);
    }
};

Back to top page