Path Link-Cut Tree
(ds/dynamic_tree/path_link_cut_tree.hpp)

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

Overview

m1une::ds::PathLinkCutTree<Monoid> maintains a dynamic forest. It supports linking two trees, cutting an existing edge, rerooting a represented tree, and querying a monoid product on a path.

The value is stored on 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 implementation supports non-commutative monoids. prod(u, v) returns the product in path order from u to v.

Template Parameter

Monoid must satisfy m1une::monoid::IsMonoid:

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

op(a, b) should be associative, and id() should be its identity.

Construction

PathLinkCutTree<Monoid> lct;
PathLinkCutTree<Monoid> lct(n);
PathLinkCutTree<Monoid> lct(values);

PathLinkCutTree(n) creates n isolated vertices initialized with Monoid::id().
PathLinkCutTree(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 Monoid::make(value), Monoid::make(value, index), or static_cast<T>(value) is available.

Methods

Method	Description	Complexity
`int size()`	Number of link-cut-tree vertices.	$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 tree.	Amortized $O(\log N)$
`int component_root(v)`	Returns the represented root of `v`’s tree.	Amortized $O(\log N)$
`bool connected(u, v)`	Returns whether `u` and `v` are in the same tree.	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 trees. Returns whether it was added.	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 `u` and `v` are already connected.	Amortized $O(\log N)$
`bool cut(u, v)`	Removes edge `(u, v)` if it exists. On success, the resulting trees are rooted at `u` and `v`.	Amortized $O(\log N)$
`bool cut_edge(edge_id)`	Removes a helper edge created by `link_edge`. On success, the endpoint trees 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)`	Returns the monoid 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)$

prod, path_size, and kth_vertex require u and v to be connected. This is checked by assert.

Path Order

For non-commutative monoids, order matters. If the represented path is:

u - a - b - v

then:

lct.prod(u, v) == op(op(op(value[u], value[a]), value[b]), value[v])
lct.prod(v, u) == op(op(op(value[v], value[b]), value[a]), value[u])

Internally the structure keeps both the normal and reversed aggregate of every splay subtree, so path reversal by evert is safe for non-commutative monoids.

Represented Roots And LCA

evert(v) changes the represented root of the tree containing v.

The following public methods reroot internally:

link(u, v) first reroots u’s tree at u. If it succeeds, the merged tree keeps the original represented root of v’s tree. If it returns false because u and v were already connected, that tree may be left rooted at u.
link_edge(u, v, value) uses link twice. If it succeeds, the merged tree keeps the original represented root of v’s tree.
cut(u, v) first reroots at u. If it succeeds, the tree containing u is rooted at u, and the tree containing v is rooted at v. If it returns false after u != v, u’s tree may still be left rooted at u.
cut_edge(edge_id) uses cut twice. If it succeeds, the original u-side tree is rooted at the stored u endpoint, the original v-side tree 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.

Other public methods may expose or splay vertices, but they do not change the represented root.

lca(u, v) is computed with respect to the current represented root. If the root matters, call evert(r) immediately before lca:

lct.evert(r);
int x = lct.lca(u, v);

Example: Vertex Path Sum

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

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

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

    std::cout << lct.prod(2, 3) << "\n"; // 3 + 2 + 4 = 9

    lct.set(1, 10);
    std::cout << lct.prod(2, 3) << "\n"; // 3 + 10 + 4 = 17
}

Example: Edge Path Sum

Store original vertices with identity values. link_edge creates one extra link-cut-tree vertex for the edge value and links it between the two endpoints.

using Sum = m1une::monoid::Add<long long>;
m1une::ds::PathLinkCutTree<Sum> lct(n);

int edge_id = lct.link_edge(u, v, weight);

long long distance = lct.prod(a, b);
lct.set_edge(edge_id, new_weight);

This also makes cut easy:

lct.cut_edge(edge_id);

Notes

All complexities are amortized. The represented forest must remain a forest: link(u, v) returns false if u and v are already connected, link_edge(u, v, value) returns -1 in that case, and cut(u, v) returns false if (u, v) is not an existing represented edge.

size() includes helper edge nodes created by link_edge. The original vertex ids remain unchanged.

This implementation maintains path aggregates only. It does not maintain subtree aggregates of the represented tree. For a variant with subtree-query helpers, use LinkCutTree.

For path updates with lazy propagation, use LazyPathLinkCutTree.

Depends on

Monoid Concept (monoid/concept.hpp)

Verified with

verify/ds/dynamic_tree/path_link_cut_tree.test.cpp

Code

#ifndef M1UNE_PATH_LINK_CUT_TREE_HPP
#define M1UNE_PATH_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::IsMonoid Monoid>
struct PathLinkCutTree {
    using T = typename Monoid::value_type;

   private:
    struct Node {
        int left = -1;
        int right = -1;
        int parent = -1;
        bool rev = false;
        int size = 1;
        T value = Monoid::id();
        T prod = Monoid::id();
        T rev_prod = Monoid::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) { Monoid::make(x); } ||
        requires(U x, int i) { Monoid::make(x, i); } ||
        std::convertible_to<U, T>
    )
    static T make_node_value(const U& value, int index) {
        if constexpr (requires(U x) { Monoid::make(x); }) {
            return Monoid::make(value);
        } else if constexpr (requires(U x, int i) { Monoid::make(x, i); }) {
            return Monoid::make(value, index);
        } else {
            return static_cast<T>(value);
        }
    }

    int child_size(int node) const {
        return node == -1 ? 0 : _nodes[node].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);
        T left_prod = x.left == -1 ? Monoid::id() : _nodes[x.left].prod;
        T right_prod = x.right == -1 ? Monoid::id() : _nodes[x.right].prod;
        T left_rev_prod = x.left == -1 ? Monoid::id() : _nodes[x.left].rev_prod;
        T right_rev_prod = x.right == -1 ? Monoid::id() : _nodes[x.right].rev_prod;
        x.prod = Monoid::op(Monoid::op(left_prod, x.value), right_prod);
        x.rev_prod = Monoid::op(Monoid::op(right_rev_prod, x.value), left_rev_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);
            _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:
    PathLinkCutTree() = default;

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

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

    explicit PathLinkCutTree(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) { Monoid::make(x); } ||
        requires(U x, int i) { Monoid::make(x, i); } ||
        std::convertible_to<U, T>
    )
    explicit PathLinkCutTree(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 = Monoid::id()) {
        Node node;
        node.value = value;
        node.prod = value;
        node.rev_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;
        _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) { Monoid::make(x); } ||
        requires(U x, int i) { Monoid::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) { Monoid::make(x); } ||
        requires(U x, int i) { Monoid::make(x, i); } ||
        std::convertible_to<U, T>
    )
    void set(int v, const U& value) {
        set(v, make_node_value(value, v));
    }

    void evert(int v) {
        check_vertex(v);
        access(v);
        apply_reverse(v);
    }

    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;
    }

    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);
    }

    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;
        _nodes[u].parent = v;
        return true;
    }

    int link_edge(int u, int v, const T& value = Monoid::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) { Monoid::make(x); } ||
        requires(U x, int i) { Monoid::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()));
    }

    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;
    }

    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) { Monoid::make(x); } ||
        requires(U x, int i) { Monoid::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)));
    }

    T prod(int u, int v) {
        check_vertex(u);
        check_vertex(v);
        assert(connected(u, v));
        evert(u);
        access(v);
        return _nodes[v].prod;
    }

    T path_prod(int u, int v) {
        return prod(u, v);
    }

    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;
    }

    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);
    }
};

}  // namespace ds
}  // namespace m1une

#endif  // M1UNE_PATH_LINK_CUT_TREE_HPP

#line 1 "ds/dynamic_tree/path_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/path_link_cut_tree.hpp"

namespace m1une {
namespace ds {

template <m1une::monoid::IsMonoid Monoid>
struct PathLinkCutTree {
    using T = typename Monoid::value_type;

   private:
    struct Node {
        int left = -1;
        int right = -1;
        int parent = -1;
        bool rev = false;
        int size = 1;
        T value = Monoid::id();
        T prod = Monoid::id();
        T rev_prod = Monoid::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) { Monoid::make(x); } ||
        requires(U x, int i) { Monoid::make(x, i); } ||
        std::convertible_to<U, T>
    )
    static T make_node_value(const U& value, int index) {
        if constexpr (requires(U x) { Monoid::make(x); }) {
            return Monoid::make(value);
        } else if constexpr (requires(U x, int i) { Monoid::make(x, i); }) {
            return Monoid::make(value, index);
        } else {
            return static_cast<T>(value);
        }
    }

    int child_size(int node) const {
        return node == -1 ? 0 : _nodes[node].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);
        T left_prod = x.left == -1 ? Monoid::id() : _nodes[x.left].prod;
        T right_prod = x.right == -1 ? Monoid::id() : _nodes[x.right].prod;
        T left_rev_prod = x.left == -1 ? Monoid::id() : _nodes[x.left].rev_prod;
        T right_rev_prod = x.right == -1 ? Monoid::id() : _nodes[x.right].rev_prod;
        x.prod = Monoid::op(Monoid::op(left_prod, x.value), right_prod);
        x.rev_prod = Monoid::op(Monoid::op(right_rev_prod, x.value), left_rev_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);
            _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:
    PathLinkCutTree() = default;

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

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

    explicit PathLinkCutTree(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) { Monoid::make(x); } ||
        requires(U x, int i) { Monoid::make(x, i); } ||
        std::convertible_to<U, T>
    )
    explicit PathLinkCutTree(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 = Monoid::id()) {
        Node node;
        node.value = value;
        node.prod = value;
        node.rev_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;
        _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) { Monoid::make(x); } ||
        requires(U x, int i) { Monoid::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) { Monoid::make(x); } ||
        requires(U x, int i) { Monoid::make(x, i); } ||
        std::convertible_to<U, T>
    )
    void set(int v, const U& value) {
        set(v, make_node_value(value, v));
    }

    void evert(int v) {
        check_vertex(v);
        access(v);
        apply_reverse(v);
    }

    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;
    }

    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);
    }

    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;
        _nodes[u].parent = v;
        return true;
    }

    int link_edge(int u, int v, const T& value = Monoid::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) { Monoid::make(x); } ||
        requires(U x, int i) { Monoid::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()));
    }

    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;
    }

    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) { Monoid::make(x); } ||
        requires(U x, int i) { Monoid::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)));
    }

    T prod(int u, int v) {
        check_vertex(u);
        check_vertex(v);
        assert(connected(u, v));
        evert(u);
        access(v);
        return _nodes[v].prod;
    }

    T path_prod(int u, int v) {
        return prod(u, v);
    }

    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;
    }

    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);
    }
};

}  // namespace ds
}  // namespace m1une

m1une's library

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

Path Link-Cut Tree
(ds/dynamic_tree/path_link_cut_tree.hpp)

Overview

Template Parameter

Construction

Methods

Path Order

Represented Roots And LCA

Example: Vertex Path Sum

Example: Edge Path Sum

Notes

Depends on

Verified with

Code

Path Link-Cut Tree (ds/dynamic_tree/path_link_cut_tree.hpp)

Overview

Template Parameter

Construction

Methods

Path Order

Represented Roots And LCA

Example: Vertex Path Sum

Example: Edge Path Sum

Notes

Depends on

Verified with

Code

Path Link-Cut Tree
(ds/dynamic_tree/path_link_cut_tree.hpp)