Lazy Link-Cut Tree
(ds/dynamic_tree/lazy_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_link_cut_tree.hpp"

Overview

m1une::ds::LazyLinkCutTree<ActedGroup> maintains a dynamic forest. It supports linking two trees, cutting edges, rerooting represented trees, querying path products, applying lazy updates on paths, 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 structure keeps a cached aggregate of virtual child subtrees, while path lazy propagation updates only preferred-path vertices. Path operations and subtree queries are amortized $O(\log N)$.

Template Parameter

ActedGroup must satisfy m1une::acted_monoid::IsCommutativeActedGroup:

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

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

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

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

op must be associative and commutative, id() must be its identity, and inv(x) must satisfy op(x, inv(x)) == id(). As with LazyPathLinkCutTree, mapping must distribute over op.

Construction

LazyLinkCutTree<ActedGroup> lct;
LazyLinkCutTree<ActedGroup> lct(n);
LazyLinkCutTree<ActedGroup> lct(values);

LazyLinkCutTree(n) creates n isolated vertices initialized with ActedGroup::id().
LazyLinkCutTree(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 ActedGroup::make(value), ActedGroup::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)$
`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 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)$
`T get_edge(edge_id)`	Pushes pending updates and 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)`	Value 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)`	Value 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)`	Value 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)`	Value 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.

Unlike non-lazy LinkCutTree::get, LazyLinkCutTree::get is not const, because it must expose the vertex and push pending lazy operations first.

Example

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

int main() {
    using AM = m1une::acted_monoid::RangeAddRangeSum<long long>;
    m1une::ds::LazyLinkCutTree<AM> 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);

    lct.apply(2, 4, 10);
    std::cout << lct.path_prod(2, 4).sum << "\n";     // 54
    std::cout << lct.subtree_prod(0, 1).sum << "\n";  // 54

    lct.apply(0, 3, 5);
    std::cout << lct.subtree_prod(0, 1).sum << "\n";  // 64
}

Example: Rooted Tree Helpers

using AM = m1une::acted_monoid::RangeAddRangeSum<long long>;
m1une::ds::LazyLinkCutTree<AM> 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);

lct.apply(3, 4, 10);  // adds 10 to vertices 3, 2, and 4

long long whole = lct.component_prod(0).sum;       // 45
long long branch = lct.branch_prod(0, 4).sum;      // 42
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).sum;  // 27

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 ActedGroup::id() 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), apply(u, v, f), 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 supports lazy path updates, but it does not provide subtree updates. A path update must not touch virtual side subtrees, so the implementation keeps preferred-path values and virtual-subtree aggregates as separate cached values.

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

Acted Monoid Concept (acted_monoid/concept.hpp)

Verified with

verify/ds/dynamic_tree/lazy_link_cut_tree.test.cpp

Code

#ifndef M1UNE_LAZY_LINK_CUT_TREE_HPP
#define M1UNE_LAZY_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::IsCommutativeActedGroup ActedGroup>
struct LazyLinkCutTree {
    using T = typename ActedGroup::value_type;
    using F = typename ActedGroup::operator_type;

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

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

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

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

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

    T child_rake_prod(int node) const {
        return node == -1 ? ActedGroup::id() : _nodes[node].rake_prod;
    }

    T node_subtree_prod(int node) const {
        const Node& x = _nodes[node];
        return ActedGroup::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.rake_size = x.virtual_size + child_rake_size(x.left) + child_rake_size(x.right);
        x.all_size = x.size + x.rake_size;
        x.prod = ActedGroup::op(ActedGroup::op(child_prod(x.left), x.value), child_prod(x.right));
        x.rev_prod = ActedGroup::op(ActedGroup::op(child_rev_prod(x.right), x.value), child_rev_prod(x.left));
        x.rake_prod = ActedGroup::op(ActedGroup::op(child_rake_prod(x.left), x.virtual_prod),
                                      child_rake_prod(x.right));
        x.all_prod = ActedGroup::op(x.prod, x.rake_prod);
    }

    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 = ActedGroup::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 = ActedGroup::op(x.virtual_prod, ActedGroup::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 apply_operator(int node, const F& f) {
        if (node == -1) return;
        Node& x = _nodes[node];
        x.value = ActedGroup::mapping(f, x.value);
        x.prod = ActedGroup::mapping(f, x.prod);
        x.rev_prod = ActedGroup::mapping(f, x.rev_prod);
        x.all_prod = ActedGroup::op(x.prod, x.rake_prod);
        x.lazy = ActedGroup::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 = ActedGroup::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);
            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:
    LazyLinkCutTree() = default;

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

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

    explicit LazyLinkCutTree(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) { ActedGroup::make(x); } ||
        requires(U x, int i) { ActedGroup::make(x, i); } ||
        std::convertible_to<U, T>
    )
    explicit LazyLinkCutTree(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 = ActedGroup::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) { ActedGroup::make(x); } ||
        requires(U x, int i) { ActedGroup::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) { ActedGroup::make(x); } ||
        requires(U x, int i) { ActedGroup::make(x, i); } ||
        std::convertible_to<U, T>
    )
    void set(int v, const U& value) {
        set(v, make_node_value(value, v));
    }

    // Applies `f` to one vertex.
    void apply(int v, const F& f) {
        check_vertex(v);
        access(v);
        _nodes[v].value = ActedGroup::mapping(f, _nodes[v].value);
        update(v);
    }

    // Applies `f` to the path from `u` to `v`. Internally calls `evert(u)`,
    // so the represented root may change.
    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);
    }

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

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

    // 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 ActedGroup::op(whole, ActedGroup::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_LAZY_LINK_CUT_TREE_HPP

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

namespace m1une {
namespace ds {

template <m1une::acted_monoid::IsCommutativeActedGroup ActedGroup>
struct LazyLinkCutTree {
    using T = typename ActedGroup::value_type;
    using F = typename ActedGroup::operator_type;

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

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

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

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

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

    T child_rake_prod(int node) const {
        return node == -1 ? ActedGroup::id() : _nodes[node].rake_prod;
    }

    T node_subtree_prod(int node) const {
        const Node& x = _nodes[node];
        return ActedGroup::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.rake_size = x.virtual_size + child_rake_size(x.left) + child_rake_size(x.right);
        x.all_size = x.size + x.rake_size;
        x.prod = ActedGroup::op(ActedGroup::op(child_prod(x.left), x.value), child_prod(x.right));
        x.rev_prod = ActedGroup::op(ActedGroup::op(child_rev_prod(x.right), x.value), child_rev_prod(x.left));
        x.rake_prod = ActedGroup::op(ActedGroup::op(child_rake_prod(x.left), x.virtual_prod),
                                      child_rake_prod(x.right));
        x.all_prod = ActedGroup::op(x.prod, x.rake_prod);
    }

    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 = ActedGroup::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 = ActedGroup::op(x.virtual_prod, ActedGroup::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 apply_operator(int node, const F& f) {
        if (node == -1) return;
        Node& x = _nodes[node];
        x.value = ActedGroup::mapping(f, x.value);
        x.prod = ActedGroup::mapping(f, x.prod);
        x.rev_prod = ActedGroup::mapping(f, x.rev_prod);
        x.all_prod = ActedGroup::op(x.prod, x.rake_prod);
        x.lazy = ActedGroup::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 = ActedGroup::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);
            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:
    LazyLinkCutTree() = default;

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

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

    explicit LazyLinkCutTree(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) { ActedGroup::make(x); } ||
        requires(U x, int i) { ActedGroup::make(x, i); } ||
        std::convertible_to<U, T>
    )
    explicit LazyLinkCutTree(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 = ActedGroup::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) { ActedGroup::make(x); } ||
        requires(U x, int i) { ActedGroup::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) { ActedGroup::make(x); } ||
        requires(U x, int i) { ActedGroup::make(x, i); } ||
        std::convertible_to<U, T>
    )
    void set(int v, const U& value) {
        set(v, make_node_value(value, v));
    }

    // Applies `f` to one vertex.
    void apply(int v, const F& f) {
        check_vertex(v);
        access(v);
        _nodes[v].value = ActedGroup::mapping(f, _nodes[v].value);
        update(v);
    }

    // Applies `f` to the path from `u` to `v`. Internally calls `evert(u)`,
    // so the represented root may change.
    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);
    }

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

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

    // 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 ActedGroup::op(whole, ActedGroup::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

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

Overview

Template Parameter

Construction

Methods

Example

Example: Rooted Tree Helpers

Notes

Depends on

Verified with

Code

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

Overview

Template Parameter

Construction

Methods

Example

Example: Rooted Tree Helpers

Notes

Depends on

Verified with

Code

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