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

View this file on GitHub
Last update: 2026-06-21 04:34:53+09:00
Include: #include "ds/dynamic_tree/lazy_path_link_cut_tree.hpp"

Overview

m1une::ds::LazyPathLinkCutTree<ActedMonoid> maintains a dynamic forest with path queries and path updates.

It is the lazy-propagation version of PathLinkCutTree. The value monoid gives the path query, and the operator monoid gives the path update. This matches the same acted-monoid style used by LazySegtree.

Typical examples:

path add, path sum
path affine update, path sum
path assign, path max
edge path updates by storing each edge as an extra node

Template Parameter

ActedMonoid must satisfy m1une::acted_monoid::IsActedMonoid:

struct AM {
    using value_type = T;
    using operator_type = F;

    static T id();
    static T op(const T& a, const T& b);

    static F op_id();
    static F op_comp(const F& f, const F& g); // f(g(x))

    static T mapping(const F& f, const T& x);
};

The important law is that mapping must distribute over the value monoid:

mapping(f, op(a, b)) == op(mapping(f, a), mapping(f, b))

The implementation does not support position-dependent lazy operators such as arithmetic-progression updates. There is no op_shift hook here, because a link-cut tree reverses preferred paths dynamically.

Construction

LazyPathLinkCutTree<ActedMonoid> lct;
LazyPathLinkCutTree<ActedMonoid> lct(n);
LazyPathLinkCutTree<ActedMonoid> lct(values);

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

Construction from std::vector<U> is supported when ActedMonoid::make(value), ActedMonoid::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)$
`T get(v)`	Pushes pending updates and returns the stored value of vertex `v`.	Amortized $O(\log N)$
`T operator[](v)`	Alias for `get(v)`.	Amortized $O(\log N)$
`void set(v, value)`	Updates the value of vertex `v`.	Amortized $O(\log N)$
`void apply(v, f)`	Applies operator `f` to one vertex.	Amortized $O(\log N)$
`void apply(u, v, f)`	Applies operator `f` to every link-cut-tree vertex on the path from `u` to `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)$
`T get_edge(edge_id)`	Returns the value stored in the helper edge node.	Amortized $O(\log N)$
`void set_edge(edge_id, value)`	Updates the value stored in the helper edge node.	Amortized $O(\log N)$
`void apply_edge(edge_id, f)`	Applies operator `f` to one 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, apply(u, v, f), path_size, and kth_vertex require u and v to be connected. This is checked by assert.

Unlike PathLinkCutTree::get, LazyPathLinkCutTree::get is not const, because it must expose the vertex and push pending lazy operations first.

Path Order

prod(u, v) returns the value monoid product in path order from u to v. The implementation stores both forward and reversed products, so non-commutative value monoids are supported as long as the lazy mapping distributes over that monoid.

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), apply(u, v, f), 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: Path Add, Path Sum

#include "acted_monoid/range_add_range_sum.hpp"
#include "ds/dynamic_tree/lazy_path_link_cut_tree.hpp"
#include <iostream>
#include <vector>

int main() {
    using AM = m1une::acted_monoid::RangeAddRangeSum<long long>;
    m1une::ds::LazyPathLinkCutTree<AM> 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).sum << "\n"; // 3 + 2 + 4 = 9

    lct.apply(2, 3, 10);
    std::cout << lct.prod(2, 3).sum << "\n"; // 13 + 12 + 14 = 39
}

Example: Edge Path Add, Edge Path Sum

Initialize original vertices with ActedMonoid::id(), whose size is 0 for RangeAddRangeSum. Then edge nodes are the only values affected by path updates and path sums.

using AM = m1une::acted_monoid::RangeAddRangeSum<long long>;
m1une::ds::LazyPathLinkCutTree<AM> lct(n);

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

lct.apply(a, b, 5);              // add 5 to every edge on path a-b
long long distance = lct.prod(a, b).sum;

lct.set_edge(edge_id, new_weight);
lct.cut_edge(edge_id);

Notes

All complexities are amortized. size() includes helper edge nodes created by link_edge; 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 LazyLinkCutTree.

Depends on

Acted Monoid Concept (acted_monoid/concept.hpp)

Verified with

verify/ds/dynamic_tree/lazy_path_link_cut_tree.test.cpp

Code

#ifndef M1UNE_LAZY_PATH_LINK_CUT_TREE_HPP
#define M1UNE_LAZY_PATH_LINK_CUT_TREE_HPP 1

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

#include "../../acted_monoid/concept.hpp"

namespace m1une {
namespace ds {

template <m1une::acted_monoid::IsActedMonoid ActedMonoid>
struct LazyPathLinkCutTree {
    using T = typename ActedMonoid::value_type;
    using F = typename ActedMonoid::operator_type;

   private:
    struct Node {
        int left = -1;
        int right = -1;
        int parent = -1;
        bool rev = false;
        int size = 1;
        T value = ActedMonoid::id();
        T prod = ActedMonoid::id();
        T rev_prod = ActedMonoid::id();
        F lazy = ActedMonoid::op_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) { ActedMonoid::make(x); } ||
        requires(U x, int i) { ActedMonoid::make(x, i); } ||
        std::convertible_to<U, T>
    )
    static T make_node_value(const U& value, int index) {
        if constexpr (requires(U x) { ActedMonoid::make(x); }) {
            return ActedMonoid::make(value);
        } else if constexpr (requires(U x, int i) { ActedMonoid::make(x, i); }) {
            return ActedMonoid::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 ? ActedMonoid::id() : _nodes[x.left].prod;
        T right_prod = x.right == -1 ? ActedMonoid::id() : _nodes[x.right].prod;
        T left_rev_prod = x.left == -1 ? ActedMonoid::id() : _nodes[x.left].rev_prod;
        T right_rev_prod = x.right == -1 ? ActedMonoid::id() : _nodes[x.right].rev_prod;
        x.prod = ActedMonoid::op(ActedMonoid::op(left_prod, x.value), right_prod);
        x.rev_prod = ActedMonoid::op(ActedMonoid::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 apply_operator(int node, const F& f) {
        if (node == -1) return;
        Node& x = _nodes[node];
        x.value = ActedMonoid::mapping(f, x.value);
        x.prod = ActedMonoid::mapping(f, x.prod);
        x.rev_prod = ActedMonoid::mapping(f, x.rev_prod);
        x.lazy = ActedMonoid::op_comp(f, x.lazy);
    }

    void push(int node) {
        if (node == -1) return;
        Node& x = _nodes[node];
        if (x.rev) {
            apply_reverse(x.left);
            apply_reverse(x.right);
            x.rev = false;
        }
        apply_operator(x.left, x.lazy);
        apply_operator(x.right, x.lazy);
        x.lazy = ActedMonoid::op_id();
    }

    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:
    LazyPathLinkCutTree() = default;

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

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

    explicit LazyPathLinkCutTree(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) { ActedMonoid::make(x); } ||
        requires(U x, int i) { ActedMonoid::make(x, i); } ||
        std::convertible_to<U, T>
    )
    explicit LazyPathLinkCutTree(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 = ActedMonoid::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) { ActedMonoid::make(x); } ||
        requires(U x, int i) { ActedMonoid::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};
    }

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

    T operator[](int v) {
        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) { ActedMonoid::make(x); } ||
        requires(U x, int i) { ActedMonoid::make(x, i); } ||
        std::convertible_to<U, T>
    )
    void set(int v, const U& value) {
        set(v, make_node_value(value, v));
    }

    void apply(int v, const F& f) {
        check_vertex(v);
        access(v);
        _nodes[v].value = ActedMonoid::mapping(f, _nodes[v].value);
        update(v);
    }

    void apply(int u, int v, const F& f) {
        check_vertex(u);
        check_vertex(v);
        assert(connected(u, v));
        evert(u);
        access(v);
        apply_operator(v, f);
    }

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

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

    void apply_edge(int edge_id, const F& f) {
        apply(edge_node(edge_id), f);
    }

    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_LAZY_PATH_LINK_CUT_TREE_HPP

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



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

#line 1 "acted_monoid/concept.hpp"



#line 5 "acted_monoid/concept.hpp"

namespace m1une {
namespace acted_monoid {

// Concept defining the requirements for an Acted Monoid.
template <typename AM>
concept IsActedMonoid = requires(typename AM::value_type a, typename AM::value_type b, typename AM::operator_type f,
                                 typename AM::operator_type g) {
    // 1. Value Monoid
    typename AM::value_type;
    { AM::id() } -> std::same_as<typename AM::value_type>;
    { AM::op(a, b) } -> std::same_as<typename AM::value_type>;

    // 2. Operator Monoid
    typename AM::operator_type;
    { AM::op_id() } -> std::same_as<typename AM::operator_type>;
    { AM::op_comp(f, g) } -> std::same_as<typename AM::operator_type>;  // Composition order: f(g(x))

    // 3. Mapping: Operator x Value -> Value
    { AM::mapping(f, a) } -> std::same_as<typename AM::value_type>;
};

// Concept for acted monoids whose value monoid is a commutative group.
// The value operation must obey commutativity and inverse laws.
template <typename AM>
concept IsCommutativeActedGroup = IsActedMonoid<AM> && requires(typename AM::value_type a) {
    { AM::inv(a) } -> std::same_as<typename AM::value_type>;
};

}  // namespace acted_monoid
}  // namespace m1une


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

namespace m1une {
namespace ds {

template <m1une::acted_monoid::IsActedMonoid ActedMonoid>
struct LazyPathLinkCutTree {
    using T = typename ActedMonoid::value_type;
    using F = typename ActedMonoid::operator_type;

   private:
    struct Node {
        int left = -1;
        int right = -1;
        int parent = -1;
        bool rev = false;
        int size = 1;
        T value = ActedMonoid::id();
        T prod = ActedMonoid::id();
        T rev_prod = ActedMonoid::id();
        F lazy = ActedMonoid::op_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) { ActedMonoid::make(x); } ||
        requires(U x, int i) { ActedMonoid::make(x, i); } ||
        std::convertible_to<U, T>
    )
    static T make_node_value(const U& value, int index) {
        if constexpr (requires(U x) { ActedMonoid::make(x); }) {
            return ActedMonoid::make(value);
        } else if constexpr (requires(U x, int i) { ActedMonoid::make(x, i); }) {
            return ActedMonoid::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 ? ActedMonoid::id() : _nodes[x.left].prod;
        T right_prod = x.right == -1 ? ActedMonoid::id() : _nodes[x.right].prod;
        T left_rev_prod = x.left == -1 ? ActedMonoid::id() : _nodes[x.left].rev_prod;
        T right_rev_prod = x.right == -1 ? ActedMonoid::id() : _nodes[x.right].rev_prod;
        x.prod = ActedMonoid::op(ActedMonoid::op(left_prod, x.value), right_prod);
        x.rev_prod = ActedMonoid::op(ActedMonoid::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 apply_operator(int node, const F& f) {
        if (node == -1) return;
        Node& x = _nodes[node];
        x.value = ActedMonoid::mapping(f, x.value);
        x.prod = ActedMonoid::mapping(f, x.prod);
        x.rev_prod = ActedMonoid::mapping(f, x.rev_prod);
        x.lazy = ActedMonoid::op_comp(f, x.lazy);
    }

    void push(int node) {
        if (node == -1) return;
        Node& x = _nodes[node];
        if (x.rev) {
            apply_reverse(x.left);
            apply_reverse(x.right);
            x.rev = false;
        }
        apply_operator(x.left, x.lazy);
        apply_operator(x.right, x.lazy);
        x.lazy = ActedMonoid::op_id();
    }

    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:
    LazyPathLinkCutTree() = default;

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

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

    explicit LazyPathLinkCutTree(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) { ActedMonoid::make(x); } ||
        requires(U x, int i) { ActedMonoid::make(x, i); } ||
        std::convertible_to<U, T>
    )
    explicit LazyPathLinkCutTree(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 = ActedMonoid::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) { ActedMonoid::make(x); } ||
        requires(U x, int i) { ActedMonoid::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};
    }

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

    T operator[](int v) {
        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) { ActedMonoid::make(x); } ||
        requires(U x, int i) { ActedMonoid::make(x, i); } ||
        std::convertible_to<U, T>
    )
    void set(int v, const U& value) {
        set(v, make_node_value(value, v));
    }

    void apply(int v, const F& f) {
        check_vertex(v);
        access(v);
        _nodes[v].value = ActedMonoid::mapping(f, _nodes[v].value);
        update(v);
    }

    void apply(int u, int v, const F& f) {
        check_vertex(u);
        check_vertex(v);
        assert(connected(u, v));
        evert(u);
        access(v);
        apply_operator(v, f);
    }

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

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

    void apply_edge(int edge_id, const F& f) {
        apply(edge_node(edge_id), f);
    }

    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

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

Overview

Template Parameter

Construction

Methods

Path Order

Represented Roots And LCA

Example: Path Add, Path Sum

Example: Edge Path Add, Edge Path Sum

Notes

Depends on

Verified with

Code

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

Overview

Template Parameter

Construction

Methods

Path Order

Represented Roots And LCA

Example: Path Add, Path Sum

Example: Edge Path Add, Edge Path Sum

Notes

Depends on

Verified with

Code

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