Link Cut Tree (tree/link_cut.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-10-28 09:15:43+07:00
• Include: #include "tree/link_cut.hpp"

Description

Link Cut Tree (LCT) is a data structure for maintaining a forest of trees and supporting link, cut, and path operations. It uses splay trees internally to achieve $\mathcal O(\log n)$ amortized time per operation. Users must define a node type that inherits from lct_node.

Example node to handle subtree sum:

struct node : lct_node<node> {
    // use the default constructor
    using lct_node::lct_node;

    i64 val = 0, sum = 0, light = 0;

    void set(i32 x) { val = x; }
    void add(i32 x) { val += x; }

    void pull() { sum = $(l)->sum + $(r)->sum + val + light; }
    void add_light(ptr c) { light += c->sum; }
    void sub_light(ptr c) { light -= c->sum; }
};

Operations

• LCT<node>(int n = 0)
  • Constructs LCT with n nodes
  • Time complexity: $\mathcal O(n)$
• auto operator[](int i)
  • Returns pointer to node i
  • Time complexity: $\mathcal O(1)$
• int id(ptr t)
  • Returns the ID of node t
  • Time complexity: $\mathcal O(1)$

Note: All operations from splay onwards have static pointer variants that take ptr (pointer) arguments instead of int (vertex ID) arguments.

• void splay(int v)
  • Splays node v to root of its splay tree
  • Time complexity: $\mathcal O(\log n)$ amortized
• void expose(int v)
  • Exposes path from v to root, making v the root of its splay tree
  • Time complexity: $\mathcal O(\log n)$ amortized
• void expose_path(int u, int v)
  • Exposes path from u to v
  • Time complexity: $\mathcal O(\log n)$ amortized
• void evert(int v)
  • Makes v the root of its tree
  • Time complexity: $\mathcal O(\log n)$ amortized
• void link(int v, int p)
  • Links node v as a child of p (must be root of its tree)
  • Time complexity: $\mathcal O(\log n)$ amortized
• void cut(int v, int p)
  • Cuts edge between v and p
  • Time complexity: $\mathcal O(\log n)$ amortized
• int lca(int u, int v)
  • Returns LCA of u and v, or -1 if not connected
  • Time complexity: $\mathcal O(\log n)$ amortized
• template<class... T> void set(int v, T &&...x)
  • Exposes v and calls set on the node
  • Time complexity: $\mathcal O(\log n)$ amortized
• template<class... T> void add(int v, T &&...x)
  • Exposes v and calls add on the node
  • Time complexity: $\mathcal O(\log n)$ amortized

Verified with

• test/yosupo/graph/incremental_minimum_spanning_forest.test.cpp
• test/yosupo/tree/dynamic_tree_vertex_add_subtree_sum.test.cpp
• test/yosupo/tree/dynamic_tree_vertex_set_path_composite.test.cpp
• test/yosupo/tree/lca_link_cut.test.cpp

Code

#pragma once

template<class node> struct LCT {
    using ptr = node *;
    vector<node> nodes;

    LCT(int n = 0) : nodes(n) {}

    auto operator[](int i) { return &nodes[i]; }
    int id(ptr t) { return int(t - &nodes[0]); }

    void splay(int v) { splay(&nodes[v]); }
    void expose(int v) { expose(&nodes[v]); }
    void expose_path(int u, int v) { evert(u), expose(v); }
    void evert(int v) { evert(&nodes[v]); }
    void link(int v, int p) { link(&nodes[v], &nodes[p]); }
    void cut(int v, int p) { cut(&nodes[v], &nodes[p]); }
    int lca(int u, int v) {
        ptr l = lca(&nodes[u], &nodes[v]);
        return l ? id(l) : -1;
    }
    template<class... T> void set(int v, T &&...x) {
        expose(v), nodes[v].set(x...);
    }
    template<class... T> void add(int v, T &&...x) {
        expose(v), nodes[v].add(x...);
    }

    static void splay(ptr t) {
        for (t->_push(); state(t); rot(t)) {
            ptr p = t->p, g = p->p;
            if (g) g->_push();
            p->_push(), t->_push();
            if (state(p)) rot(state(t) == state(p) ? p : t);
        }
    }
    static ptr expose(ptr t) {
        ptr prv = 0;
        for (ptr cur = t; cur; cur = cur->p) {
            splay(cur);
            if (cur->r) cur->_add_light(cur->r);
            if (prv) cur->_sub_light(prv);
            attach(cur, 1, exchange(prv, cur));
        }
        splay(t);
        return prv;
    }
    static void evert(ptr t) { expose(t), t->_flip(); }
    static void link(ptr v, ptr p) {
        evert(v), expose(p);
        assert(!v->p && !p->r);
        attach(p, 1, v);
    }
    static void cut(ptr v, ptr p) {
        evert(p), expose(v);
        assert(!v->p && v->l == p);
        attach(v, 0, p->p = 0);
    }
    static ptr lca(ptr u, ptr v) {
        if (u == v) return u;
        expose(u);
        ptr l = expose(v);
        return u->p ? l : 0;
    }

    static ptr &ch(ptr t, bool d) { return d ? t->r : t->l; }
    static void attach(ptr p, int d, ptr c) {
        if (c) c->p = p;
        ch(p, d) = c, p->pull();
    }
    static int state(ptr t) {
        if (!t->p) return 0;
        return t == t->p->l ? -1 : t == t->p->r ? 1 : 0;
    }
    static void rot(ptr t) {
        ptr p = t->p, g = p->p;
        int d = state(t) == 1, dp = state(p);
        t->p = p->p;
        if (g) dp ? attach(g, dp == 1, t) : g->_change_light(p, t);
        attach(p, d, ch(t, !d));
        attach(t, !d, p);
    }
};

template<class node> struct lct_node {
    using ptr = node *;
    static ptr $(ptr t) {
        static node nil;
        return t ?: &nil;
    }
    ptr p = 0, l = 0, r = 0;
    bool rev = 0;

    node *as_derived() { return (node *)this; };
    void _push() {
        if (exchange(rev, 0)) $(l)->_flip(), $(r)->_flip();
        if constexpr (has_push<node>) as_derived()->push();
    }
    void _flip() {
        swap(l, r), rev ^= 1;
        if constexpr (has_flip<node>) as_derived()->flip();
    }

    void _add_light(ptr c) {
        if constexpr (has_add_light<node>) as_derived()->add_light(c);
    }
    void _sub_light(ptr c) {
        if constexpr (has_sub_light<node>) as_derived()->sub_light(c);
    }
    void _change_light(ptr prv, ptr cur) {
        if constexpr (has_change_light<node>)
            as_derived()->change_light(prv, cur);
    }

// rip compile time
#define CHECK(a) \
    template<class T, class = void> struct has_##a##_t : false_type {}; \
    template<class T> struct has_##a##_t<T, void_t<decltype(&T::a)>> : true_type {}; \
    template<class T> static constexpr bool has_##a = has_##a##_t<T>::value;
    CHECK(push) CHECK(flip)
    CHECK(add_light) CHECK(sub_light) CHECK(change_light)
#undef CHECK
};

#line 2 "tree/link_cut.hpp"

template<class node> struct LCT {
    using ptr = node *;
    vector<node> nodes;

    LCT(int n = 0) : nodes(n) {}

    auto operator[](int i) { return &nodes[i]; }
    int id(ptr t) { return int(t - &nodes[0]); }

    void splay(int v) { splay(&nodes[v]); }
    void expose(int v) { expose(&nodes[v]); }
    void expose_path(int u, int v) { evert(u), expose(v); }
    void evert(int v) { evert(&nodes[v]); }
    void link(int v, int p) { link(&nodes[v], &nodes[p]); }
    void cut(int v, int p) { cut(&nodes[v], &nodes[p]); }
    int lca(int u, int v) {
        ptr l = lca(&nodes[u], &nodes[v]);
        return l ? id(l) : -1;
    }
    template<class... T> void set(int v, T &&...x) {
        expose(v), nodes[v].set(x...);
    }
    template<class... T> void add(int v, T &&...x) {
        expose(v), nodes[v].add(x...);
    }

    static void splay(ptr t) {
        for (t->_push(); state(t); rot(t)) {
            ptr p = t->p, g = p->p;
            if (g) g->_push();
            p->_push(), t->_push();
            if (state(p)) rot(state(t) == state(p) ? p : t);
        }
    }
    static ptr expose(ptr t) {
        ptr prv = 0;
        for (ptr cur = t; cur; cur = cur->p) {
            splay(cur);
            if (cur->r) cur->_add_light(cur->r);
            if (prv) cur->_sub_light(prv);
            attach(cur, 1, exchange(prv, cur));
        }
        splay(t);
        return prv;
    }
    static void evert(ptr t) { expose(t), t->_flip(); }
    static void link(ptr v, ptr p) {
        evert(v), expose(p);
        assert(!v->p && !p->r);
        attach(p, 1, v);
    }
    static void cut(ptr v, ptr p) {
        evert(p), expose(v);
        assert(!v->p && v->l == p);
        attach(v, 0, p->p = 0);
    }
    static ptr lca(ptr u, ptr v) {
        if (u == v) return u;
        expose(u);
        ptr l = expose(v);
        return u->p ? l : 0;
    }

    static ptr &ch(ptr t, bool d) { return d ? t->r : t->l; }
    static void attach(ptr p, int d, ptr c) {
        if (c) c->p = p;
        ch(p, d) = c, p->pull();
    }
    static int state(ptr t) {
        if (!t->p) return 0;
        return t == t->p->l ? -1 : t == t->p->r ? 1 : 0;
    }
    static void rot(ptr t) {
        ptr p = t->p, g = p->p;
        int d = state(t) == 1, dp = state(p);
        t->p = p->p;
        if (g) dp ? attach(g, dp == 1, t) : g->_change_light(p, t);
        attach(p, d, ch(t, !d));
        attach(t, !d, p);
    }
};

template<class node> struct lct_node {
    using ptr = node *;
    static ptr $(ptr t) {
        static node nil;
        return t ?: &nil;
    }
    ptr p = 0, l = 0, r = 0;
    bool rev = 0;

    node *as_derived() { return (node *)this; };
    void _push() {
        if (exchange(rev, 0)) $(l)->_flip(), $(r)->_flip();
        if constexpr (has_push<node>) as_derived()->push();
    }
    void _flip() {
        swap(l, r), rev ^= 1;
        if constexpr (has_flip<node>) as_derived()->flip();
    }

    void _add_light(ptr c) {
        if constexpr (has_add_light<node>) as_derived()->add_light(c);
    }
    void _sub_light(ptr c) {
        if constexpr (has_sub_light<node>) as_derived()->sub_light(c);
    }
    void _change_light(ptr prv, ptr cur) {
        if constexpr (has_change_light<node>)
            as_derived()->change_light(prv, cur);
    }

// rip compile time
#define CHECK(a) \
    template<class T, class = void> struct has_##a##_t : false_type {}; \
    template<class T> struct has_##a##_t<T, void_t<decltype(&T::a)>> : true_type {}; \
    template<class T> static constexpr bool has_##a = has_##a##_t<T>::value;
    CHECK(push) CHECK(flip)
    CHECK(add_light) CHECK(sub_light) CHECK(change_light)
#undef CHECK
};

Back to top page