Link-Cut Tree
(ds/dynamic_tree/link_cut_tree.hpp)

View this file on GitHub
Last update: 2026-07-16 20:44:42+09:00
Include: #include "ds/dynamic_tree/link_cut_tree.hpp"

Overview

m1une::ds::LinkCutTree<Group> maintains a dynamic forest. It supports linking two trees, cutting edges, rerooting represented trees, querying path products, and querying rooted subtree products and sizes.

The value is stored on link-cut-tree vertices. If you need edge values, create one extra link-cut-tree vertex for each original edge and connect it between the two endpoints. The link_edge helper does this for you.

The values must form a commutative group. The inverse lets the structure update aggregates of virtual child subtrees in constant time whenever access changes the preferred path. Path and subtree queries are both amortized $O(\log N)$.

Template Parameter

Group must satisfy m1une::monoid::IsCommutativeGroup:

struct G {
    using value_type = T;
    static T id();
    static T op(const T& a, const T& b);
    static T inv(const T& x);
};

op must be associative and commutative, id() must be its identity, and inv(x) must satisfy op(x, inv(x)) == id().

Construction

LinkCutTree<Group> lct;
LinkCutTree<Group> lct(n);
LinkCutTree<Group> lct(values);

LinkCutTree(n) creates n isolated vertices initialized with Group::id().
LinkCutTree(values) creates one isolated vertex for each value.
add_vertex(value) appends a new isolated vertex and returns its index.

As with Segtree, construction from std::vector<U> is supported when Group::make(value), Group::make(value, index), or static_cast<T>(value) is available.

Methods

Method	Description	Complexity
`int size()`	Number of link-cut-tree vertices, including helper edge nodes.	$O(1)$
`bool empty()`	Whether there are no vertices.	$O(1)$
`int add_vertex(value)`	Adds one isolated vertex and returns its id.	Amortized $O(1)$
`int edge_count()`	Number of edge helpers created by `link_edge`.	$O(1)$
`bool edge_alive(edge_id)`	Whether the helper edge is currently linked.	$O(1)$
`int edge_node(edge_id)`	Link-cut-tree vertex id storing this edge’s value.	$O(1)$
`std::pair<int, int> edge_endpoints(edge_id)`	Original endpoints passed to `link_edge`.	$O(1)$
`const T& get(v)`	Returns the stored value of vertex `v`.	$O(1)$
`const T& operator[](v)`	Alias for `get(v)`.	$O(1)$
`void set(v, value)`	Updates the value of vertex `v`.	Amortized $O(\log N)$
`void evert(v)`	Makes `v` the represented root of its component.	Amortized $O(\log N)$
`void reroot(v)`	Alias for `evert(v)`.	Amortized $O(\log N)$
`int component_root(v)`	Returns the represented root of `v`’s component.	Amortized $O(\log N)$
`int root(v)`	Alias for `component_root(v)`.	Amortized $O(\log N)$
`bool connected(u, v)`	Returns whether `u` and `v` are in the same component.	Amortized $O(\log N)$
`bool same(u, v)`	Alias for `connected(u, v)`.	Amortized $O(\log N)$
`bool link(u, v)`	Adds edge `(u, v)` if they are in different components. Returns whether it was added.	Amortized $O(\log N)$
`bool link_parent(child, parent)`	Rooted-tree spelling of `link(child, parent)`; after a successful link, the merged component keeps the original represented root of `parent`’s component.	Amortized $O(\log N)$
`int link_edge(u, v, value)`	Adds an edge-value node between `u` and `v`. Returns an edge id, or `-1` if already connected.	Amortized $O(\log N)$
`bool cut(u, v)`	Removes edge `(u, v)` if it exists. On success, the resulting components are rooted at `u` and `v`.	Amortized $O(\log N)$
`bool cut_parent(v)`	Removes the current parent edge of `v` with respect to the represented root. On success, `v` becomes the root of the detached child-side component.	Amortized $O(\log N)$
`bool cut_edge(edge_id)`	Removes a helper edge created by `link_edge`. On success, the endpoint components are rooted at the stored endpoints.	Amortized $O(\log N)$
`const T& get_edge(edge_id)`	Returns the value stored in the helper edge node.	$O(1)$
`void set_edge(edge_id, value)`	Updates the value stored in the helper edge node.	Amortized $O(\log N)$
`T prod(u, v)`	Group product on the path from `u` to `v`.	Amortized $O(\log N)$
`T path_prod(u, v)`	Alias for `prod(u, v)`.	Amortized $O(\log N)$
`int path_size(u, v)`	Number of link-cut-tree vertices on the path from `u` to `v`.	Amortized $O(\log N)$
`int kth_vertex(u, v, k)`	Returns the `k`-th vertex on the path from `u` to `v`, zero-indexed.	Amortized $O(\log N)$
`int lca(u, v)`	Returns the LCA with respect to the current represented root, or `-1` if disconnected.	Amortized $O(\log N)$
`T component_prod(v)`	Group product of the whole connected component containing `v`.	Amortized $O(\log N)$
`int component_size(v)`	Number of link-cut-tree vertices in the component containing `v`.	Amortized $O(\log N)$
`int child_toward(root, v)`	Child of `root` lying on the path from `root` to `v`; requires `root != v`.	Amortized $O(\log N)$
`T branch_prod(root, v)`	Group product of the entire branch of `root` that contains `v`.	Amortized $O(\log N)$
`int branch_size(root, v)`	Size of the entire branch of `root` that contains `v`.	Amortized $O(\log N)$
`int parent(root, v)`	Parent of `v` when rooted at `root`, or `-1` if `root == v`.	Amortized $O(\log N)$
`T subtree_prod(root, v)`	Group product of the rooted subtree.	Amortized $O(\log N)$
`T subtree_prod(v)`	Uses the current represented root of `v`’s component.	Amortized $O(\log N)$
`int subtree_size(root, v)`	Number of link-cut-tree vertices in the subtree of `v` when rooted at `root`.	Amortized $O(\log N)$
`int subtree_size(v)`	Uses the current represented root of `v`’s component.	Amortized $O(\log N)$
`T subtree_prod_excluding_child(root, v, child)`	Product of `v`’s rooted subtree excluding `child`’s subtree.	Amortized $O(\log N)$
`int subtree_size_excluding_child(root, v, child)`	Size of `v`’s rooted subtree excluding `child`’s subtree.	Amortized $O(\log N)$

Path and rooted-subtree queries assert that the queried vertices are connected. child_toward(root, v), branch_prod(root, v), and branch_size(root, v) also assert root != v. The excluding-child helpers assert that child is a child of v when the represented tree is rooted at root.

Example

#include "ds/dynamic_tree/link_cut_tree.hpp"
#include "monoid/add.hpp"
#include <iostream>
#include <vector>

int main() {
    using Sum = m1une::monoid::Add<long long>;
    m1une::ds::LinkCutTree<Sum> lct(std::vector<long long>{1, 2, 3, 4, 5});

    lct.link(0, 1);
    lct.link(1, 2);
    lct.link(1, 3);
    lct.link(3, 4);

    std::cout << lct.path_prod(2, 4) << "\n";     // 3 + 2 + 4 + 5 = 14
    std::cout << lct.subtree_prod(0, 1) << "\n";  // 2 + 3 + 4 + 5 = 14
}

Example: Rooted Tree Helpers

using Sum = m1une::monoid::Add<long long>;
m1une::ds::LinkCutTree<Sum> lct(std::vector<long long>{1, 2, 3, 4, 5});

// Rooted shape:
// 0
// +- 1
// +- 2
//    +- 3
//    +- 4
lct.link_parent(1, 0);
lct.link_parent(2, 0);
lct.link_parent(3, 2);
lct.link_parent(4, 2);
lct.reroot(0);

long long whole = lct.component_prod(0);       // 1 + 2 + 3 + 4 + 5 = 15
long long branch = lct.branch_prod(0, 4);      // 3 + 4 + 5 = 12
int p = lct.parent(0, 4);                      // 2
int c = lct.child_toward(0, 4);                // 2
long long without_4 = lct.subtree_prod_excluding_child(0, 2, 4);  // 3 + 4 = 7

lct.cut_parent(4);  // cuts edge 2-4 without changing the represented root first

Notes

link_edge creates helper vertices for edge values. Subtree sizes and products include those helper vertices. Initialize original vertices with the group identity when you want subtree products over edge values only.

evert(v) and reroot(v) change the represented root of the component to v.

The following public methods reroot internally:

link(u, v) first reroots u’s component at u. If it succeeds, the merged component keeps the original represented root of v’s component. If it returns false because u and v were already connected, that component may be left rooted at u.
link_parent(child, parent) is the same operation as link(child, parent). If it succeeds, it reroots the child-side component at child, attaches it under parent, and preserves the original represented root of the parent-side component.
link_edge(u, v, value) uses link twice. If it succeeds, the merged component keeps the original represented root of v’s component.
cut(u, v) first reroots at u. If it succeeds, the component containing u is rooted at u, and the component containing v is rooted at v. If it returns false after u != v, u’s component may still be left rooted at u.
cut_parent(v) does not call evert. If it succeeds, the old represented root remains the root of the parent-side component, and v becomes the represented root of the detached child-side component.
cut_edge(edge_id) uses cut twice. If it succeeds, the original u-side component is rooted at the stored u endpoint, the original v-side component is rooted at the stored v endpoint, and the helper edge node is isolated.
prod(u, v), path_prod(u, v), path_size(u, v), and kth_vertex(u, v, k) reroot at u, so the represented root becomes u.
subtree_prod(root, v), subtree_size(root, v), child_toward(root, v), branch_prod(root, v), branch_size(root, v), parent(root, v), subtree_prod_excluding_child(root, v, child), and subtree_size_excluding_child(root, v, child) reroot at root, so the represented root becomes root.

Other public methods may expose or splay vertices, but they do not change the represented root. In particular, lca(u, v) uses the current represented root, and subtree_prod(v) and subtree_size(v) use the current represented root.

This structure does not support non-commutative subtree products. A represented subtree has no canonical linear order, and the virtual-child aggregate relies on commutativity and inv.

Depends on

Monoid Concept (monoid/concept.hpp)

Required by

Verified with

Code

#ifndef M1UNE_LINK_CUT_TREE_HPP
#define M1UNE_LINK_CUT_TREE_HPP 1

#include <cassert>
#include <concepts>
#include <type_traits>
#include <utility>
#include <vector>

#include "../../monoid/concept.hpp"

namespace m1une {
namespace ds {

template <m1une::monoid::IsCommutativeGroup Group>
struct LinkCutTree {
    using T = typename Group::value_type;

   private:
    struct Node {
        int left = -1;
        int right = -1;
        int parent = -1;
        bool rev = false;
        int size = 1;
        int virtual_size = 0;
        int all_size = 1;
        T value = Group::id();
        T prod = Group::id();
        T rev_prod = Group::id();
        T virtual_prod = Group::id();
        T all_prod = Group::id();
    };

    struct EdgeInfo {
        int u = -1;
        int v = -1;
        int node = -1;
        bool alive = false;
    };

    std::vector<Node> _nodes;
    std::vector<EdgeInfo> _edges;
    std::vector<int> _path_buffer;

    static T make_node_value(const T& value, int) {
        return value;
    }

    static T make_node_value(T&& value, int) {
        return std::move(value);
    }

    template <class U>
    requires (!std::same_as<U, T>) && (
        requires(U x) { Group::make(x); } ||
        requires(U x, int i) { Group::make(x, i); } ||
        std::convertible_to<U, T>
    )
    static T make_node_value(const U& value, int index) {
        if constexpr (requires(U x) { Group::make(x); }) {
            return Group::make(value);
        } else if constexpr (requires(U x, int i) { Group::make(x, i); }) {
            return Group::make(value, index);
        } else {
            return static_cast<T>(value);
        }
    }

    int child_size(int node) const {
        return node == -1 ? 0 : _nodes[node].size;
    }

    int child_all_size(int node) const {
        return node == -1 ? 0 : _nodes[node].all_size;
    }

    T child_prod(int node) const {
        return node == -1 ? Group::id() : _nodes[node].prod;
    }

    T child_rev_prod(int node) const {
        return node == -1 ? Group::id() : _nodes[node].rev_prod;
    }

    T child_all_prod(int node) const {
        return node == -1 ? Group::id() : _nodes[node].all_prod;
    }

    T node_subtree_prod(int node) const {
        const Node& x = _nodes[node];
        return Group::op(x.value, x.virtual_prod);
    }

    int node_subtree_size(int node) const {
        return 1 + _nodes[node].virtual_size;
    }

    bool is_splay_root(int node) const {
        int parent = _nodes[node].parent;
        return parent == -1 || (_nodes[parent].left != node && _nodes[parent].right != node);
    }

    void update(int node) {
        Node& x = _nodes[node];
        x.size = 1 + child_size(x.left) + child_size(x.right);
        x.all_size = 1 + x.virtual_size + child_all_size(x.left) + child_all_size(x.right);
        x.prod = Group::op(Group::op(child_prod(x.left), x.value), child_prod(x.right));
        x.rev_prod = Group::op(Group::op(child_rev_prod(x.right), x.value), child_rev_prod(x.left));
        x.all_prod = Group::op(Group::op(child_all_prod(x.left), x.value),
                                Group::op(x.virtual_prod, child_all_prod(x.right)));
    }

    void add_virtual_child(int node, int child) {
        if (child == -1) return;
        Node& x = _nodes[node];
        x.virtual_size += _nodes[child].all_size;
        x.virtual_prod = Group::op(x.virtual_prod, _nodes[child].all_prod);
    }

    void remove_virtual_child(int node, int child) {
        if (child == -1) return;
        Node& x = _nodes[node];
        x.virtual_size -= _nodes[child].all_size;
        x.virtual_prod = Group::op(x.virtual_prod, Group::inv(_nodes[child].all_prod));
    }

    void apply_reverse(int node) {
        if (node == -1) return;
        Node& x = _nodes[node];
        std::swap(x.left, x.right);
        std::swap(x.prod, x.rev_prod);
        x.rev = !x.rev;
    }

    void push(int node) {
        if (node == -1 || !_nodes[node].rev) return;
        apply_reverse(_nodes[node].left);
        apply_reverse(_nodes[node].right);
        _nodes[node].rev = false;
    }

    void push_to(int node) {
        _path_buffer.clear();
        int cur = node;
        _path_buffer.push_back(cur);
        while (!is_splay_root(cur)) {
            cur = _nodes[cur].parent;
            _path_buffer.push_back(cur);
        }
        for (int i = int(_path_buffer.size()) - 1; i >= 0; i--) push(_path_buffer[i]);
    }

    void rotate(int node) {
        int parent = _nodes[node].parent;
        int grand = _nodes[parent].parent;
        bool is_right = _nodes[parent].right == node;
        int middle = is_right ? _nodes[node].left : _nodes[node].right;

        if (!is_splay_root(parent)) {
            if (_nodes[grand].left == parent) {
                _nodes[grand].left = node;
            } else {
                _nodes[grand].right = node;
            }
        }
        _nodes[node].parent = grand;

        if (is_right) {
            _nodes[node].left = parent;
            _nodes[parent].right = middle;
        } else {
            _nodes[node].right = parent;
            _nodes[parent].left = middle;
        }
        if (middle != -1) _nodes[middle].parent = parent;
        _nodes[parent].parent = node;

        update(parent);
        update(node);
    }

    void splay(int node) {
        push_to(node);
        while (!is_splay_root(node)) {
            int parent = _nodes[node].parent;
            int grand = _nodes[parent].parent;
            if (!is_splay_root(parent)) {
                bool zig_zig = (_nodes[parent].left == node) == (_nodes[grand].left == parent);
                rotate(zig_zig ? parent : node);
            }
            rotate(node);
        }
    }

    int access(int node) {
        int last = -1;
        for (int cur = node; cur != -1; cur = _nodes[cur].parent) {
            splay(cur);
            add_virtual_child(cur, _nodes[cur].right);
            remove_virtual_child(cur, last);
            _nodes[cur].right = last;
            if (last != -1) _nodes[last].parent = cur;
            update(cur);
            last = cur;
        }
        splay(node);
        return last;
    }

    void check_vertex(int v) const {
        assert(0 <= v && v < int(_nodes.size()));
    }

    void check_edge(int edge_id) const {
        assert(0 <= edge_id && edge_id < int(_edges.size()));
    }

   public:
    LinkCutTree() = default;

    explicit LinkCutTree(int n) {
        assert(0 <= n);
        _nodes.reserve(n);
        for (int i = 0; i < n; i++) add_vertex();
    }

    explicit LinkCutTree(const std::vector<T>& values) {
        _nodes.reserve(values.size());
        for (int i = 0; i < int(values.size()); i++) add_vertex(values[i]);
    }

    explicit LinkCutTree(std::vector<T>&& values) {
        _nodes.reserve(values.size());
        for (int i = 0; i < int(values.size()); i++) add_vertex(std::move(values[i]));
    }

    template <class U>
    requires (!std::same_as<U, T>) && (
        requires(U x) { Group::make(x); } ||
        requires(U x, int i) { Group::make(x, i); } ||
        std::convertible_to<U, T>
    )
    explicit LinkCutTree(const std::vector<U>& values) {
        _nodes.reserve(values.size());
        for (int i = 0; i < int(values.size()); i++) add_vertex(make_node_value(values[i], i));
    }

    int size() const {
        return int(_nodes.size());
    }

    bool empty() const {
        return _nodes.empty();
    }

    int add_vertex(const T& value = Group::id()) {
        Node node;
        node.value = value;
        node.prod = value;
        node.rev_prod = value;
        node.all_prod = value;
        _nodes.push_back(std::move(node));
        return int(_nodes.size()) - 1;
    }

    int add_vertex(T&& value) {
        Node node;
        node.value = std::move(value);
        node.prod = node.value;
        node.rev_prod = node.value;
        node.all_prod = node.value;
        _nodes.push_back(std::move(node));
        return int(_nodes.size()) - 1;
    }

    template <class U>
    requires (!std::same_as<std::remove_cvref_t<U>, T>) && (
        requires(U x) { Group::make(x); } ||
        requires(U x, int i) { Group::make(x, i); } ||
        std::convertible_to<U, T>
    )
    int add_vertex(const U& value) {
        return add_vertex(make_node_value(value, size()));
    }

    int edge_count() const {
        return int(_edges.size());
    }

    bool edge_alive(int edge_id) const {
        check_edge(edge_id);
        return _edges[edge_id].alive;
    }

    int edge_node(int edge_id) const {
        check_edge(edge_id);
        return _edges[edge_id].node;
    }

    std::pair<int, int> edge_endpoints(int edge_id) const {
        check_edge(edge_id);
        return {_edges[edge_id].u, _edges[edge_id].v};
    }

    const T& get(int v) const {
        check_vertex(v);
        return _nodes[v].value;
    }

    const T& operator[](int v) const {
        return get(v);
    }

    void set(int v, const T& value) {
        check_vertex(v);
        access(v);
        _nodes[v].value = value;
        update(v);
    }

    void set(int v, T&& value) {
        check_vertex(v);
        access(v);
        _nodes[v].value = std::move(value);
        update(v);
    }

    template <class U>
    requires (!std::same_as<std::remove_cvref_t<U>, T>) && (
        requires(U x) { Group::make(x); } ||
        requires(U x, int i) { Group::make(x, i); } ||
        std::convertible_to<U, T>
    )
    void set(int v, const U& value) {
        set(v, make_node_value(value, v));
    }

    // Makes `v` the represented root of its component.
    void evert(int v) {
        check_vertex(v);
        access(v);
        apply_reverse(v);
    }

    // Alias for `evert(v)`; changes the represented root to `v`.
    void reroot(int v) {
        evert(v);
    }

    // Returns the current represented root of `v`'s component.
    int component_root(int v) {
        check_vertex(v);
        access(v);
        int cur = v;
        push(cur);
        while (_nodes[cur].left != -1) {
            cur = _nodes[cur].left;
            push(cur);
        }
        splay(cur);
        return cur;
    }

    // Alias for `component_root(v)`.
    int root(int v) {
        return component_root(v);
    }

    bool connected(int u, int v) {
        check_vertex(u);
        check_vertex(v);
        if (u == v) return true;
        return component_root(u) == component_root(v);
    }

    bool same(int u, int v) {
        return connected(u, v);
    }

    // Links two components. Internally calls `evert(u)`, so the represented root may change.
    bool link(int u, int v) {
        check_vertex(u);
        check_vertex(v);
        if (u == v) return false;
        evert(u);
        if (component_root(v) == u) return false;
        access(v);
        _nodes[u].parent = v;
        add_virtual_child(v, u);
        update(v);
        return true;
    }

    // Links `child` under `parent`. This is the same operation as `link(child, parent)`;
    // it internally calls `evert(child)`, so that side's represented root may change.
    bool link_parent(int child, int parent) {
        return link(child, parent);
    }

    int link_edge(int u, int v, const T& value = Group::id()) {
        check_vertex(u);
        check_vertex(v);
        if (u == v || connected(u, v)) return -1;
        int edge_id = int(_edges.size());
        int node = add_vertex(value);
        _edges.push_back(EdgeInfo{u, v, node, true});
        bool ok1 = link(u, node);
        bool ok2 = link(node, v);
        assert(ok1 && ok2);
        return edge_id;
    }

    int link_edge(int u, int v, T&& value) {
        check_vertex(u);
        check_vertex(v);
        if (u == v || connected(u, v)) return -1;
        int edge_id = int(_edges.size());
        int node = add_vertex(std::move(value));
        _edges.push_back(EdgeInfo{u, v, node, true});
        bool ok1 = link(u, node);
        bool ok2 = link(node, v);
        assert(ok1 && ok2);
        return edge_id;
    }

    template <class U>
    requires (!std::same_as<std::remove_cvref_t<U>, T>) && (
        requires(U x) { Group::make(x); } ||
        requires(U x, int i) { Group::make(x, i); } ||
        std::convertible_to<U, T>
    )
    int link_edge(int u, int v, const U& value) {
        check_vertex(u);
        check_vertex(v);
        if (u == v || connected(u, v)) return -1;
        return link_edge(u, v, make_node_value(value, size()));
    }

    // Cuts edge `(u, v)`. Internally calls `evert(u)`, so the represented root may change.
    bool cut(int u, int v) {
        check_vertex(u);
        check_vertex(v);
        if (u == v) return false;
        evert(u);
        access(v);
        if (_nodes[v].left != u || _nodes[u].right != -1) return false;
        _nodes[v].left = -1;
        _nodes[u].parent = -1;
        update(v);
        return true;
    }

    // Cuts the parent edge of `v` in the current represented-root orientation.
    // Unlike `cut(u, v)`, this does not call `evert`.
    bool cut_parent(int v) {
        check_vertex(v);
        access(v);
        int left = _nodes[v].left;
        if (left == -1) return false;
        _nodes[v].left = -1;
        _nodes[left].parent = -1;
        update(v);
        return true;
    }

    bool cut_edge(int edge_id) {
        check_edge(edge_id);
        EdgeInfo& edge = _edges[edge_id];
        if (!edge.alive) return false;
        bool ok1 = cut(edge.u, edge.node);
        bool ok2 = cut(edge.node, edge.v);
        if (ok1 && ok2) edge.alive = false;
        return ok1 && ok2;
    }

    const T& get_edge(int edge_id) const {
        return get(edge_node(edge_id));
    }

    void set_edge(int edge_id, const T& value) {
        set(edge_node(edge_id), value);
    }

    void set_edge(int edge_id, T&& value) {
        set(edge_node(edge_id), std::move(value));
    }

    template <class U>
    requires (!std::same_as<std::remove_cvref_t<U>, T>) && (
        requires(U x) { Group::make(x); } ||
        requires(U x, int i) { Group::make(x, i); } ||
        std::convertible_to<U, T>
    )
    void set_edge(int edge_id, const U& value) {
        set(edge_node(edge_id), make_node_value(value, edge_node(edge_id)));
    }

    // Returns the path product from `u` to `v`. Internally calls `evert(u)`,
    // so the represented root may change.
    T prod(int u, int v) {
        check_vertex(u);
        check_vertex(v);
        assert(connected(u, v));
        evert(u);
        access(v);
        return _nodes[v].prod;
    }

    // Alias for `prod(u, v)`. Internally calls `evert(u)`,
    // so the represented root may change.
    T path_prod(int u, int v) {
        return prod(u, v);
    }

    // Returns the number of vertices on path `u`-`v`. Internally calls `evert(u)`,
    // so the represented root may change.
    int path_size(int u, int v) {
        check_vertex(u);
        check_vertex(v);
        assert(connected(u, v));
        evert(u);
        access(v);
        return _nodes[v].size;
    }

    // Returns the `k`-th vertex on path `u`-`v`. Internally calls `evert(u)`,
    // so the represented root may change.
    int kth_vertex(int u, int v, int k) {
        check_vertex(u);
        check_vertex(v);
        assert(connected(u, v));
        evert(u);
        access(v);
        assert(0 <= k && k < _nodes[v].size);

        int cur = v;
        while (true) {
            push(cur);
            int left_size = child_size(_nodes[cur].left);
            if (k < left_size) {
                cur = _nodes[cur].left;
            } else if (k == left_size) {
                splay(cur);
                return cur;
            } else {
                k -= left_size + 1;
                cur = _nodes[cur].right;
            }
        }
    }

    int lca(int u, int v) {
        check_vertex(u);
        check_vertex(v);
        if (!connected(u, v)) return -1;
        if (u == v) return u;
        access(u);
        return access(v);
    }

    // Returns the aggregate of `v`'s subtree when the represented tree is rooted at `root`.
    // Internally calls `evert(root)`, so the represented root may change.
    T subtree_prod(int root, int v) {
        check_vertex(root);
        check_vertex(v);
        assert(connected(root, v));
        evert(root);
        access(v);
        return node_subtree_prod(v);
    }

    // Returns the aggregate of `v`'s subtree with respect to the current represented root.
    T subtree_prod(int v) {
        check_vertex(v);
        access(v);
        return node_subtree_prod(v);
    }

    // Returns the size of `v`'s subtree when the represented tree is rooted at `root`.
    // Internally calls `evert(root)`, so the represented root may change.
    int subtree_size(int root, int v) {
        check_vertex(root);
        check_vertex(v);
        assert(connected(root, v));
        evert(root);
        access(v);
        return node_subtree_size(v);
    }

    // Returns the size of `v`'s subtree with respect to the current represented root.
    int subtree_size(int v) {
        check_vertex(v);
        access(v);
        return node_subtree_size(v);
    }

    // Returns the aggregate of the whole connected component containing `v`.
    T component_prod(int v) {
        int r = root(v);
        return subtree_prod(r, r);
    }

    // Returns the number of vertices in the connected component containing `v`.
    int component_size(int v) {
        int r = root(v);
        return subtree_size(r, r);
    }

    // Returns the child of `root` that lies on path `root`-`v`.
    int child_toward(int root, int v) {
        check_vertex(root);
        check_vertex(v);
        assert(root != v);
        assert(connected(root, v));
        return kth_vertex(root, v, 1);
    }

    // Returns the aggregate of the entire branch of `root` that contains `v`.
    T branch_prod(int root, int v) {
        check_vertex(root);
        check_vertex(v);
        assert(root != v);
        int child = child_toward(root, v);
        return subtree_prod(root, child);
    }

    // Returns the size of the entire branch of `root` that contains `v`.
    int branch_size(int root, int v) {
        check_vertex(root);
        check_vertex(v);
        assert(root != v);
        int child = child_toward(root, v);
        return subtree_size(root, child);
    }

    // Returns the parent of `v` when rooted at `root`, or `-1` if `v == root`.
    int parent(int root, int v) {
        check_vertex(root);
        check_vertex(v);
        if (root == v) return -1;
        assert(connected(root, v));
        int d = path_size(root, v);
        assert(2 <= d);
        return kth_vertex(root, v, d - 2);
    }

    // Returns `v`'s rooted subtree aggregate excluding the child-side subtree.
    T subtree_prod_excluding_child(int root, int v, int child) {
        check_vertex(root);
        check_vertex(v);
        check_vertex(child);
        assert(parent(root, child) == v);
        T whole = subtree_prod(root, v);
        T sub = subtree_prod(root, child);
        return Group::op(whole, Group::inv(sub));
    }

    // Returns `v`'s rooted subtree size excluding the child-side subtree.
    int subtree_size_excluding_child(int root, int v, int child) {
        check_vertex(root);
        check_vertex(v);
        check_vertex(child);
        assert(parent(root, child) == v);
        return subtree_size(root, v) - subtree_size(root, child);
    }
};

}  // namespace ds
}  // namespace m1une

#endif  // M1UNE_LINK_CUT_TREE_HPP

#line 1 "ds/dynamic_tree/link_cut_tree.hpp"



#include <cassert>
#include <concepts>
#include <type_traits>
#include <utility>
#include <vector>

#line 1 "monoid/concept.hpp"



#line 5 "monoid/concept.hpp"

namespace m1une {
namespace monoid {

// Concept to check if a type satisfies the requirements of a Monoid.
// A Monoid must have a `value_type`, an identity element `id()`, and an associative binary operation `op()`.
template <typename M>
concept IsMonoid = requires(typename M::value_type a, typename M::value_type b) {
    // 1. Must define `value_type`
    typename M::value_type;

    // 2. Must have a static method `id()` returning `value_type`
    { M::id() } -> std::same_as<typename M::value_type>;

    // 3. Must have a static method `op(a, b)` returning `value_type`
    { M::op(a, b) } -> std::same_as<typename M::value_type>;
};

// Concept for groups. A type satisfying this concept must also obey the group
// laws; concepts can check the interface but not the algebraic properties.
template <typename M>
concept IsGroup = IsMonoid<M> && requires(typename M::value_type a) {
    { M::inv(a) } -> std::same_as<typename M::value_type>;
};

// Concept for commutative groups. Commutativity is a semantic requirement and
// cannot be checked by a C++ concept.
template <typename M>
concept IsCommutativeGroup = IsGroup<M>;

}  // namespace monoid
}  // namespace m1une


#line 11 "ds/dynamic_tree/link_cut_tree.hpp"

namespace m1une {
namespace ds {

template <m1une::monoid::IsCommutativeGroup Group>
struct LinkCutTree {
    using T = typename Group::value_type;

   private:
    struct Node {
        int left = -1;
        int right = -1;
        int parent = -1;
        bool rev = false;
        int size = 1;
        int virtual_size = 0;
        int all_size = 1;
        T value = Group::id();
        T prod = Group::id();
        T rev_prod = Group::id();
        T virtual_prod = Group::id();
        T all_prod = Group::id();
    };

    struct EdgeInfo {
        int u = -1;
        int v = -1;
        int node = -1;
        bool alive = false;
    };

    std::vector<Node> _nodes;
    std::vector<EdgeInfo> _edges;
    std::vector<int> _path_buffer;

    static T make_node_value(const T& value, int) {
        return value;
    }

    static T make_node_value(T&& value, int) {
        return std::move(value);
    }

    template <class U>
    requires (!std::same_as<U, T>) && (
        requires(U x) { Group::make(x); } ||
        requires(U x, int i) { Group::make(x, i); } ||
        std::convertible_to<U, T>
    )
    static T make_node_value(const U& value, int index) {
        if constexpr (requires(U x) { Group::make(x); }) {
            return Group::make(value);
        } else if constexpr (requires(U x, int i) { Group::make(x, i); }) {
            return Group::make(value, index);
        } else {
            return static_cast<T>(value);
        }
    }

    int child_size(int node) const {
        return node == -1 ? 0 : _nodes[node].size;
    }

    int child_all_size(int node) const {
        return node == -1 ? 0 : _nodes[node].all_size;
    }

    T child_prod(int node) const {
        return node == -1 ? Group::id() : _nodes[node].prod;
    }

    T child_rev_prod(int node) const {
        return node == -1 ? Group::id() : _nodes[node].rev_prod;
    }

    T child_all_prod(int node) const {
        return node == -1 ? Group::id() : _nodes[node].all_prod;
    }

    T node_subtree_prod(int node) const {
        const Node& x = _nodes[node];
        return Group::op(x.value, x.virtual_prod);
    }

    int node_subtree_size(int node) const {
        return 1 + _nodes[node].virtual_size;
    }

    bool is_splay_root(int node) const {
        int parent = _nodes[node].parent;
        return parent == -1 || (_nodes[parent].left != node && _nodes[parent].right != node);
    }

    void update(int node) {
        Node& x = _nodes[node];
        x.size = 1 + child_size(x.left) + child_size(x.right);
        x.all_size = 1 + x.virtual_size + child_all_size(x.left) + child_all_size(x.right);
        x.prod = Group::op(Group::op(child_prod(x.left), x.value), child_prod(x.right));
        x.rev_prod = Group::op(Group::op(child_rev_prod(x.right), x.value), child_rev_prod(x.left));
        x.all_prod = Group::op(Group::op(child_all_prod(x.left), x.value),
                                Group::op(x.virtual_prod, child_all_prod(x.right)));
    }

    void add_virtual_child(int node, int child) {
        if (child == -1) return;
        Node& x = _nodes[node];
        x.virtual_size += _nodes[child].all_size;
        x.virtual_prod = Group::op(x.virtual_prod, _nodes[child].all_prod);
    }

    void remove_virtual_child(int node, int child) {
        if (child == -1) return;
        Node& x = _nodes[node];
        x.virtual_size -= _nodes[child].all_size;
        x.virtual_prod = Group::op(x.virtual_prod, Group::inv(_nodes[child].all_prod));
    }

    void apply_reverse(int node) {
        if (node == -1) return;
        Node& x = _nodes[node];
        std::swap(x.left, x.right);
        std::swap(x.prod, x.rev_prod);
        x.rev = !x.rev;
    }

    void push(int node) {
        if (node == -1 || !_nodes[node].rev) return;
        apply_reverse(_nodes[node].left);
        apply_reverse(_nodes[node].right);
        _nodes[node].rev = false;
    }

    void push_to(int node) {
        _path_buffer.clear();
        int cur = node;
        _path_buffer.push_back(cur);
        while (!is_splay_root(cur)) {
            cur = _nodes[cur].parent;
            _path_buffer.push_back(cur);
        }
        for (int i = int(_path_buffer.size()) - 1; i >= 0; i--) push(_path_buffer[i]);
    }

    void rotate(int node) {
        int parent = _nodes[node].parent;
        int grand = _nodes[parent].parent;
        bool is_right = _nodes[parent].right == node;
        int middle = is_right ? _nodes[node].left : _nodes[node].right;

        if (!is_splay_root(parent)) {
            if (_nodes[grand].left == parent) {
                _nodes[grand].left = node;
            } else {
                _nodes[grand].right = node;
            }
        }
        _nodes[node].parent = grand;

        if (is_right) {
            _nodes[node].left = parent;
            _nodes[parent].right = middle;
        } else {
            _nodes[node].right = parent;
            _nodes[parent].left = middle;
        }
        if (middle != -1) _nodes[middle].parent = parent;
        _nodes[parent].parent = node;

        update(parent);
        update(node);
    }

    void splay(int node) {
        push_to(node);
        while (!is_splay_root(node)) {
            int parent = _nodes[node].parent;
            int grand = _nodes[parent].parent;
            if (!is_splay_root(parent)) {
                bool zig_zig = (_nodes[parent].left == node) == (_nodes[grand].left == parent);
                rotate(zig_zig ? parent : node);
            }
            rotate(node);
        }
    }

    int access(int node) {
        int last = -1;
        for (int cur = node; cur != -1; cur = _nodes[cur].parent) {
            splay(cur);
            add_virtual_child(cur, _nodes[cur].right);
            remove_virtual_child(cur, last);
            _nodes[cur].right = last;
            if (last != -1) _nodes[last].parent = cur;
            update(cur);
            last = cur;
        }
        splay(node);
        return last;
    }

    void check_vertex(int v) const {
        assert(0 <= v && v < int(_nodes.size()));
    }

    void check_edge(int edge_id) const {
        assert(0 <= edge_id && edge_id < int(_edges.size()));
    }

   public:
    LinkCutTree() = default;

    explicit LinkCutTree(int n) {
        assert(0 <= n);
        _nodes.reserve(n);
        for (int i = 0; i < n; i++) add_vertex();
    }

    explicit LinkCutTree(const std::vector<T>& values) {
        _nodes.reserve(values.size());
        for (int i = 0; i < int(values.size()); i++) add_vertex(values[i]);
    }

    explicit LinkCutTree(std::vector<T>&& values) {
        _nodes.reserve(values.size());
        for (int i = 0; i < int(values.size()); i++) add_vertex(std::move(values[i]));
    }

    template <class U>
    requires (!std::same_as<U, T>) && (
        requires(U x) { Group::make(x); } ||
        requires(U x, int i) { Group::make(x, i); } ||
        std::convertible_to<U, T>
    )
    explicit LinkCutTree(const std::vector<U>& values) {
        _nodes.reserve(values.size());
        for (int i = 0; i < int(values.size()); i++) add_vertex(make_node_value(values[i], i));
    }

    int size() const {
        return int(_nodes.size());
    }

    bool empty() const {
        return _nodes.empty();
    }

    int add_vertex(const T& value = Group::id()) {
        Node node;
        node.value = value;
        node.prod = value;
        node.rev_prod = value;
        node.all_prod = value;
        _nodes.push_back(std::move(node));
        return int(_nodes.size()) - 1;
    }

    int add_vertex(T&& value) {
        Node node;
        node.value = std::move(value);
        node.prod = node.value;
        node.rev_prod = node.value;
        node.all_prod = node.value;
        _nodes.push_back(std::move(node));
        return int(_nodes.size()) - 1;
    }

    template <class U>
    requires (!std::same_as<std::remove_cvref_t<U>, T>) && (
        requires(U x) { Group::make(x); } ||
        requires(U x, int i) { Group::make(x, i); } ||
        std::convertible_to<U, T>
    )
    int add_vertex(const U& value) {
        return add_vertex(make_node_value(value, size()));
    }

    int edge_count() const {
        return int(_edges.size());
    }

    bool edge_alive(int edge_id) const {
        check_edge(edge_id);
        return _edges[edge_id].alive;
    }

    int edge_node(int edge_id) const {
        check_edge(edge_id);
        return _edges[edge_id].node;
    }

    std::pair<int, int> edge_endpoints(int edge_id) const {
        check_edge(edge_id);
        return {_edges[edge_id].u, _edges[edge_id].v};
    }

    const T& get(int v) const {
        check_vertex(v);
        return _nodes[v].value;
    }

    const T& operator[](int v) const {
        return get(v);
    }

    void set(int v, const T& value) {
        check_vertex(v);
        access(v);
        _nodes[v].value = value;
        update(v);
    }

    void set(int v, T&& value) {
        check_vertex(v);
        access(v);
        _nodes[v].value = std::move(value);
        update(v);
    }

    template <class U>
    requires (!std::same_as<std::remove_cvref_t<U>, T>) && (
        requires(U x) { Group::make(x); } ||
        requires(U x, int i) { Group::make(x, i); } ||
        std::convertible_to<U, T>
    )
    void set(int v, const U& value) {
        set(v, make_node_value(value, v));
    }

    // Makes `v` the represented root of its component.
    void evert(int v) {
        check_vertex(v);
        access(v);
        apply_reverse(v);
    }

    // Alias for `evert(v)`; changes the represented root to `v`.
    void reroot(int v) {
        evert(v);
    }

    // Returns the current represented root of `v`'s component.
    int component_root(int v) {
        check_vertex(v);
        access(v);
        int cur = v;
        push(cur);
        while (_nodes[cur].left != -1) {
            cur = _nodes[cur].left;
            push(cur);
        }
        splay(cur);
        return cur;
    }

    // Alias for `component_root(v)`.
    int root(int v) {
        return component_root(v);
    }

    bool connected(int u, int v) {
        check_vertex(u);
        check_vertex(v);
        if (u == v) return true;
        return component_root(u) == component_root(v);
    }

    bool same(int u, int v) {
        return connected(u, v);
    }

    // Links two components. Internally calls `evert(u)`, so the represented root may change.
    bool link(int u, int v) {
        check_vertex(u);
        check_vertex(v);
        if (u == v) return false;
        evert(u);
        if (component_root(v) == u) return false;
        access(v);
        _nodes[u].parent = v;
        add_virtual_child(v, u);
        update(v);
        return true;
    }

    // Links `child` under `parent`. This is the same operation as `link(child, parent)`;
    // it internally calls `evert(child)`, so that side's represented root may change.
    bool link_parent(int child, int parent) {
        return link(child, parent);
    }

    int link_edge(int u, int v, const T& value = Group::id()) {
        check_vertex(u);
        check_vertex(v);
        if (u == v || connected(u, v)) return -1;
        int edge_id = int(_edges.size());
        int node = add_vertex(value);
        _edges.push_back(EdgeInfo{u, v, node, true});
        bool ok1 = link(u, node);
        bool ok2 = link(node, v);
        assert(ok1 && ok2);
        return edge_id;
    }

    int link_edge(int u, int v, T&& value) {
        check_vertex(u);
        check_vertex(v);
        if (u == v || connected(u, v)) return -1;
        int edge_id = int(_edges.size());
        int node = add_vertex(std::move(value));
        _edges.push_back(EdgeInfo{u, v, node, true});
        bool ok1 = link(u, node);
        bool ok2 = link(node, v);
        assert(ok1 && ok2);
        return edge_id;
    }

    template <class U>
    requires (!std::same_as<std::remove_cvref_t<U>, T>) && (
        requires(U x) { Group::make(x); } ||
        requires(U x, int i) { Group::make(x, i); } ||
        std::convertible_to<U, T>
    )
    int link_edge(int u, int v, const U& value) {
        check_vertex(u);
        check_vertex(v);
        if (u == v || connected(u, v)) return -1;
        return link_edge(u, v, make_node_value(value, size()));
    }

    // Cuts edge `(u, v)`. Internally calls `evert(u)`, so the represented root may change.
    bool cut(int u, int v) {
        check_vertex(u);
        check_vertex(v);
        if (u == v) return false;
        evert(u);
        access(v);
        if (_nodes[v].left != u || _nodes[u].right != -1) return false;
        _nodes[v].left = -1;
        _nodes[u].parent = -1;
        update(v);
        return true;
    }

    // Cuts the parent edge of `v` in the current represented-root orientation.
    // Unlike `cut(u, v)`, this does not call `evert`.
    bool cut_parent(int v) {
        check_vertex(v);
        access(v);
        int left = _nodes[v].left;
        if (left == -1) return false;
        _nodes[v].left = -1;
        _nodes[left].parent = -1;
        update(v);
        return true;
    }

    bool cut_edge(int edge_id) {
        check_edge(edge_id);
        EdgeInfo& edge = _edges[edge_id];
        if (!edge.alive) return false;
        bool ok1 = cut(edge.u, edge.node);
        bool ok2 = cut(edge.node, edge.v);
        if (ok1 && ok2) edge.alive = false;
        return ok1 && ok2;
    }

    const T& get_edge(int edge_id) const {
        return get(edge_node(edge_id));
    }

    void set_edge(int edge_id, const T& value) {
        set(edge_node(edge_id), value);
    }

    void set_edge(int edge_id, T&& value) {
        set(edge_node(edge_id), std::move(value));
    }

    template <class U>
    requires (!std::same_as<std::remove_cvref_t<U>, T>) && (
        requires(U x) { Group::make(x); } ||
        requires(U x, int i) { Group::make(x, i); } ||
        std::convertible_to<U, T>
    )
    void set_edge(int edge_id, const U& value) {
        set(edge_node(edge_id), make_node_value(value, edge_node(edge_id)));
    }

    // Returns the path product from `u` to `v`. Internally calls `evert(u)`,
    // so the represented root may change.
    T prod(int u, int v) {
        check_vertex(u);
        check_vertex(v);
        assert(connected(u, v));
        evert(u);
        access(v);
        return _nodes[v].prod;
    }

    // Alias for `prod(u, v)`. Internally calls `evert(u)`,
    // so the represented root may change.
    T path_prod(int u, int v) {
        return prod(u, v);
    }

    // Returns the number of vertices on path `u`-`v`. Internally calls `evert(u)`,
    // so the represented root may change.
    int path_size(int u, int v) {
        check_vertex(u);
        check_vertex(v);
        assert(connected(u, v));
        evert(u);
        access(v);
        return _nodes[v].size;
    }

    // Returns the `k`-th vertex on path `u`-`v`. Internally calls `evert(u)`,
    // so the represented root may change.
    int kth_vertex(int u, int v, int k) {
        check_vertex(u);
        check_vertex(v);
        assert(connected(u, v));
        evert(u);
        access(v);
        assert(0 <= k && k < _nodes[v].size);

        int cur = v;
        while (true) {
            push(cur);
            int left_size = child_size(_nodes[cur].left);
            if (k < left_size) {
                cur = _nodes[cur].left;
            } else if (k == left_size) {
                splay(cur);
                return cur;
            } else {
                k -= left_size + 1;
                cur = _nodes[cur].right;
            }
        }
    }

    int lca(int u, int v) {
        check_vertex(u);
        check_vertex(v);
        if (!connected(u, v)) return -1;
        if (u == v) return u;
        access(u);
        return access(v);
    }

    // Returns the aggregate of `v`'s subtree when the represented tree is rooted at `root`.
    // Internally calls `evert(root)`, so the represented root may change.
    T subtree_prod(int root, int v) {
        check_vertex(root);
        check_vertex(v);
        assert(connected(root, v));
        evert(root);
        access(v);
        return node_subtree_prod(v);
    }

    // Returns the aggregate of `v`'s subtree with respect to the current represented root.
    T subtree_prod(int v) {
        check_vertex(v);
        access(v);
        return node_subtree_prod(v);
    }

    // Returns the size of `v`'s subtree when the represented tree is rooted at `root`.
    // Internally calls `evert(root)`, so the represented root may change.
    int subtree_size(int root, int v) {
        check_vertex(root);
        check_vertex(v);
        assert(connected(root, v));
        evert(root);
        access(v);
        return node_subtree_size(v);
    }

    // Returns the size of `v`'s subtree with respect to the current represented root.
    int subtree_size(int v) {
        check_vertex(v);
        access(v);
        return node_subtree_size(v);
    }

    // Returns the aggregate of the whole connected component containing `v`.
    T component_prod(int v) {
        int r = root(v);
        return subtree_prod(r, r);
    }

    // Returns the number of vertices in the connected component containing `v`.
    int component_size(int v) {
        int r = root(v);
        return subtree_size(r, r);
    }

    // Returns the child of `root` that lies on path `root`-`v`.
    int child_toward(int root, int v) {
        check_vertex(root);
        check_vertex(v);
        assert(root != v);
        assert(connected(root, v));
        return kth_vertex(root, v, 1);
    }

    // Returns the aggregate of the entire branch of `root` that contains `v`.
    T branch_prod(int root, int v) {
        check_vertex(root);
        check_vertex(v);
        assert(root != v);
        int child = child_toward(root, v);
        return subtree_prod(root, child);
    }

    // Returns the size of the entire branch of `root` that contains `v`.
    int branch_size(int root, int v) {
        check_vertex(root);
        check_vertex(v);
        assert(root != v);
        int child = child_toward(root, v);
        return subtree_size(root, child);
    }

    // Returns the parent of `v` when rooted at `root`, or `-1` if `v == root`.
    int parent(int root, int v) {
        check_vertex(root);
        check_vertex(v);
        if (root == v) return -1;
        assert(connected(root, v));
        int d = path_size(root, v);
        assert(2 <= d);
        return kth_vertex(root, v, d - 2);
    }

    // Returns `v`'s rooted subtree aggregate excluding the child-side subtree.
    T subtree_prod_excluding_child(int root, int v, int child) {
        check_vertex(root);
        check_vertex(v);
        check_vertex(child);
        assert(parent(root, child) == v);
        T whole = subtree_prod(root, v);
        T sub = subtree_prod(root, child);
        return Group::op(whole, Group::inv(sub));
    }

    // Returns `v`'s rooted subtree size excluding the child-side subtree.
    int subtree_size_excluding_child(int root, int v, int child) {
        check_vertex(root);
        check_vertex(v);
        check_vertex(child);
        assert(parent(root, child) == v);
        return subtree_size(root, v) - subtree_size(root, child);
    }
};

}  // namespace ds
}  // namespace m1une

m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

Link-Cut Tree
(ds/dynamic_tree/link_cut_tree.hpp)

Overview

Template Parameter

Construction

Methods

Example

Example: Rooted Tree Helpers

Notes

Depends on

Required by

Verified with

Code

Link-Cut Tree (ds/dynamic_tree/link_cut_tree.hpp)

Overview

Template Parameter

Construction

Methods

Example

Example: Rooted Tree Helpers

Notes

Depends on

Required by

Verified with

Code

Link-Cut Tree
(ds/dynamic_tree/link_cut_tree.hpp)