m1une's library

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

View on GitHub

:heavy_check_mark: Rake-Compress Link-Cut Tree
(ds/dynamic_tree/rake_compress_link_cut_tree.hpp)

Overview

m1une::ds::RakeCompressLinkCutTree<TreeDPInfo> maintains a dynamic forest together with a tree DP. It separates the two aggregates needed by subtree-aware link-cut trees:

Only Point needs an inverse. In particular, affine functions on a path do not need to be invertible, and Path does not need an identity or inverse.

All dynamic-forest operations take amortized $O(\log N)$ time. Internally, each original edge is represented by a hidden helper node, but helper-node ids and operations are not exposed by the public API.

Complexity Notation

Two Interface Layers

The public interface describes only the original forest:

The class names these roles VertexId and EdgeId (both aliases of int for contest ergonomics). Internal link-cut-tree node ids are private and have no public alias or accessor.

TreeDPInfo also keeps original vertex data and original edge data separate. This removes the need for a tagged union such as NodeValue{is_vertex, ...}.

Tree DP Interface

TreeDPInfo provides four types:

using Point = ...;
using Path = ...;
using VertexValue = ...;
using EdgeValue = ...;

These types separate local original-tree data from the two aggregate levels:

Relationship between original-tree values, Point, and Path

The four panels show the operations on explicit before-and-after tree drawings. rake merges independent virtual branches at the same attachment node, make_vertex_path or make_edge_path inserts the matching original-tree value, compress concatenates adjacent ordered Path clusters, and to_point converts a child branch from Path form into a Point contribution. These callbacks change the aggregate representation, not the original-tree topology.

VertexValue and EdgeValue

VertexValue is the local data stored on an original vertex. EdgeValue is the local data stored on an original edge. Neither is an aggregate.

make_vertex_path(point, vertex_value) combines an original vertex with its already-aggregated virtual children. make_edge_path(point, edge_value) does the analogous operation for an original edge’s hidden helper node.

Point

Point represents zero or more independent child-side clusters attached at the same path node. These are the virtual children: represented-tree edges which are not currently part of the preferred path.

Their order has no meaning, so rake must be associative and commutative. Point::id() represents no virtual children. Point::inv() lets access remove a child contribution when that child enters the preferred path.

Conceptually, a node maintains:

Point virtual_children = Point::id();
virtual_children = rake(virtual_children, to_point(child_path));

Point does not include the local original-tree object at the attachment node.

Path

Path represents an ordered, nonempty preferred-path cluster. It contains the nodes on that path together with all Point contributions raked into those nodes. Its two ends have an order: the parent-side end comes before the child-side end in the current represented-root orientation.

compress(parent_side, child_side) concatenates two adjacent path clusters in that order. It must be associative, but does not need to be commutative. Reversing a represented path may change the aggregate, so each link-cut-tree node maintains both the forward and reverse Path products.

When a branch is part of the preferred path, its summary is a Path because its order matters. When that branch becomes a virtual child, it must be stored in the parent’s unordered Point aggregate instead. to_point(path) performs this conversion:

Point branch = to_point(child_path);
virtual_children = rake(virtual_children, branch);

to_point does not modify the original forest. It only changes the DP representation of an existing child branch.

A Path needs neither an identity nor an inverse.

At a link-cut-tree node, the aggregate is formed schematically as:

Path self = make_vertex_path(virtual_children, vertex_value);
// or make_edge_path(virtual_children, edge_value) at a hidden edge node
Path whole = self;
if (left_path_exists) whole = compress(left_path, whole);
if (right_path_exists) whole = compress(whole, right_path);

Point provides:

static Point id();
Point inv() const;

TreeDPInfo provides:

static Path make_vertex_path(
    const Point& virtual_children,
    const VertexValue& vertex_value
);
static Path make_edge_path(
    const Point& virtual_children,
    const EdgeValue& edge_value
);
static Point to_point(const Path& path);
static Point rake(const Point& a, const Point& b);
static Path compress(const Path& parent_side, const Path& child_side);

The operations have the following meanings:

The inverse of to_point(path) is used only when access changes a preferred child back into a virtual child or vice versa.

Methods

Method Description Complexity
VertexId add_vertex(vertex_value) Adds an isolated original vertex and returns its vertex id. Amortized $O(1)$
const VertexValue& get_vertex(VertexId v) Returns original vertex v’s value. $O(1)$
void set_vertex(VertexId v, value) Replaces original vertex v’s value. Amortized $O(\log N)$
EdgeId add_edge(VertexId u, VertexId v, edge_value) Adds an original edge and returns its edge id, or -1 if it would make a cycle. Amortized $O(\log N)$
const EdgeValue& get_edge(EdgeId e) Returns original edge e’s value. $O(1)$
void set_edge(EdgeId e, value) Replaces original edge e’s value. Amortized $O(\log N)$
bool cut_edge(EdgeId e) Removes original edge e. Amortized $O(\log N)$
void reroot(VertexId v) Makes original vertex v the represented root. Amortized $O(\log N)$
bool connected(VertexId u, VertexId v) Tests whether two original vertices are connected. Amortized $O(\log N)$
Path component_prod(VertexId v) Reroots at original vertex v and returns the whole-component cluster. Amortized $O(\log N)$

query_component(v) is an alias for component_prod(v).

vertex_count() returns the number of original vertices. edge_count() returns the number of edge ids issued so far, including cut edges. edge_alive(e) and edge_endpoints(e) inspect an original edge.

Hidden Edge Nodes

Internally, add_edge(u, v, value) subdivides the original edge with one helper node. That node lets the link-cut tree put edge data on the same preferred-path machinery as vertex data. Its id is deliberately not exposed: all public operations continue to use the original vertex id or original edge id.

Example

The following DP stores an integer on every original vertex and an affine function $f(t) = at + b$ on every original edge. The query returns the sum of all vertex values after each value is transported toward the chosen root by the edge functions on its path.

#include <iostream>

#include "ds/dynamic_tree/rake_compress_link_cut_tree.hpp"

struct AffineTreeSum {
    struct Point {
        long long sum;
        long long count;

        static Point id() {
            return Point{0, 0};
        }

        Point inv() const {
            return Point{-sum, -count};
        }
    };

    struct Path {
        long long a;
        long long b;
        long long sum;
        long long count;
    };

    struct VertexValue {
        long long value;
    };

    struct EdgeValue {
        long long a;
        long long b;
    };

    static Path make_vertex_path(
        const Point& children,
        const VertexValue& vertex
    ) {
        return Path{1, 0, children.sum + vertex.value, children.count + 1};
    }

    static Path make_edge_path(
        const Point& children,
        const EdgeValue& edge
    ) {
        return Path{
            edge.a,
            edge.b,
            children.sum * edge.a + children.count * edge.b,
            children.count
        };
    }

    static Point to_point(const Path& path) {
        return Point{path.sum, path.count};
    }

    static Point rake(const Point& x, const Point& y) {
        return Point{x.sum + y.sum, x.count + y.count};
    }

    static Path compress(const Path& parent, const Path& child) {
        return Path{
            parent.a * child.a,
            parent.a * child.b + parent.b,
            parent.sum + parent.a * child.sum + parent.b * child.count,
            parent.count + child.count
        };
    }
};

int main() {
    using LCT =
        m1une::ds::RakeCompressLinkCutTree<AffineTreeSum>;

    LCT lct;
    int u = lct.add_vertex(AffineTreeSum::VertexValue{2});
    int v = lct.add_vertex(AffineTreeSum::VertexValue{3});
    int w = lct.add_vertex(AffineTreeSum::VertexValue{5});

    // u --(t -> 2t + 1)--> v --(t -> 3t)--> w
    int uv = lct.add_edge(u, v, AffineTreeSum::EdgeValue{2, 1});
    lct.add_edge(v, w, AffineTreeSum::EdgeValue{3, 0});

    long long rooted_at_u = lct.component_prod(u).sum;
    long long rooted_at_w = lct.component_prod(w).sum;
    std::cout << rooted_at_u << '\n';  // 40
    std::cout << rooted_at_w << '\n';  // 29

    lct.set_vertex(v, AffineTreeSum::VertexValue{7});
    lct.set_edge(uv, AffineTreeSum::EdgeValue{0, 4});
}

compress(parent, child) is ordered: reversing its arguments generally changes the result. The affine coefficient may be zero because only Point requires an inverse.

Notes

component_prod(v) changes the represented root to v. Its returned Path contains the whole component, including all virtual branches attached to the preferred path exposed by rerooting.

The structure assumes that the supplied rake/compress operations describe a valid associative tree DP. It does not require affine coefficients or other path transitions to be invertible.

Verified with

Code

#ifndef M1UNE_RAKE_COMPRESS_LINK_CUT_TREE_HPP
#define M1UNE_RAKE_COMPRESS_LINK_CUT_TREE_HPP 1

#include <cassert>
#include <utility>
#include <variant>
#include <vector>

namespace m1une {
namespace ds {

// Maintains a dynamic forest whose tree DP uses two different aggregate types.
// Point is a commutative group for virtual children, while Path is an ordered
// preferred-path cluster and does not need an inverse.
template <class TreeDPInfo>
struct RakeCompressLinkCutTree {
    using Point = typename TreeDPInfo::Point;
    using Path = typename TreeDPInfo::Path;
    using VertexValue = typename TreeDPInfo::VertexValue;
    using EdgeValue = typename TreeDPInfo::EdgeValue;
    using VertexId = int;
    using EdgeId = int;

   private:
    struct Node {
        int left = -1;
        int right = -1;
        int parent = -1;
        bool rev = false;
        std::variant<VertexValue, EdgeValue> value;
        Point virtual_prod;
        Path prod;
        Path rev_prod;

        explicit Node(const VertexValue& vertex_value)
            : value(std::in_place_index<0>, vertex_value),
              virtual_prod(Point::id()),
              prod(TreeDPInfo::make_vertex_path(virtual_prod, vertex_value)),
              rev_prod(prod) {}

        explicit Node(std::in_place_index_t<1>, const EdgeValue& edge_value)
            : value(std::in_place_index<1>, edge_value),
              virtual_prod(Point::id()),
              prod(TreeDPInfo::make_edge_path(virtual_prod, edge_value)),
              rev_prod(prod) {}
    };

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

    std::vector<Node> _nodes;
    std::vector<int> _vertex_nodes;
    std::vector<OriginalEdge> _edges;
    std::vector<int> _path_buffer;

    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];
        Path self = x.value.index() == 0
            ? TreeDPInfo::make_vertex_path(x.virtual_prod, std::get<0>(x.value))
            : TreeDPInfo::make_edge_path(x.virtual_prod, std::get<1>(x.value));
        x.prod = self;
        x.rev_prod = self;

        if (x.left != -1) {
            x.prod = TreeDPInfo::compress(_nodes[x.left].prod, x.prod);
            x.rev_prod = TreeDPInfo::compress(x.rev_prod, _nodes[x.left].rev_prod);
        }
        if (x.right != -1) {
            x.prod = TreeDPInfo::compress(x.prod, _nodes[x.right].prod);
            x.rev_prod = TreeDPInfo::compress(_nodes[x.right].rev_prod, x.rev_prod);
        }
    }

    void add_virtual_child(int node, int child) {
        if (child == -1) return;
        Point contribution = TreeDPInfo::to_point(_nodes[child].prod);
        _nodes[node].virtual_prod = TreeDPInfo::rake(_nodes[node].virtual_prod, contribution);
    }

    void remove_virtual_child(int node, int child) {
        if (child == -1) return;
        Point contribution = TreeDPInfo::to_point(_nodes[child].prod);
        _nodes[node].virtual_prod = TreeDPInfo::rake(_nodes[node].virtual_prod, contribution.inv());
    }

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

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

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

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

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

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

        update(parent);
        update(node);
    }

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

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

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

    void check_vertex(VertexId vertex) const {
        assert(0 <= vertex && vertex < int(_vertex_nodes.size()));
    }

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

    int vertex_node(VertexId vertex) const {
        check_vertex(vertex);
        return _vertex_nodes[vertex];
    }

    int add_edge_node(const EdgeValue& edge_value) {
        _nodes.emplace_back(std::in_place_index<1>, edge_value);
        return int(_nodes.size()) - 1;
    }

    void set_vertex_node_value(int node, const VertexValue& vertex_value) {
        check_node(node);
        access(node);
        _nodes[node].value.template emplace<0>(vertex_value);
        update(node);
    }

    void set_edge_node_value(int node, const EdgeValue& edge_value) {
        check_node(node);
        access(node);
        _nodes[node].value.template emplace<1>(edge_value);
        update(node);
    }

    void evert_node(int node) {
        check_node(node);
        access(node);
        apply_reverse(node);
    }

    int component_root_node(int node) {
        check_node(node);
        access(node);
        int cur = node;
        push(cur);
        while (_nodes[cur].left != -1) {
            cur = _nodes[cur].left;
            push(cur);
        }
        splay(cur);
        return cur;
    }

    bool connected_nodes(int u, int v) {
        if (u == v) return true;
        return component_root_node(u) == component_root_node(v);
    }

    bool link_nodes(int u, int v) {
        check_node(u);
        check_node(v);
        if (u == v) return false;
        evert_node(u);
        if (component_root_node(v) == u) return false;
        access(v);
        _nodes[u].parent = v;
        add_virtual_child(v, u);
        update(v);
        return true;
    }

    bool cut_nodes(int u, int v) {
        check_node(u);
        check_node(v);
        if (u == v) return false;
        evert_node(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;
    }

   public:
    RakeCompressLinkCutTree() = default;

    explicit RakeCompressLinkCutTree(const std::vector<VertexValue>& values) {
        _nodes.reserve(values.size());
        _vertex_nodes.reserve(values.size());
        for (const VertexValue& value : values) add_vertex(value);
    }

    int vertex_count() const {
        return int(_vertex_nodes.size());
    }

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

    VertexId add_vertex(const VertexValue& vertex_value) {
        VertexValue value = vertex_value;
        int node = int(_nodes.size());
        _nodes.emplace_back(value);
        _vertex_nodes.push_back(node);
        return int(_vertex_nodes.size()) - 1;
    }

    const VertexValue& get_vertex(VertexId vertex) const {
        return std::get<0>(_nodes[vertex_node(vertex)].value);
    }

    void set_vertex(VertexId vertex, const VertexValue& vertex_value) {
        set_vertex_node_value(vertex_node(vertex), vertex_value);
    }

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

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

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

    const EdgeValue& get_edge(EdgeId edge_id) const {
        check_edge(edge_id);
        return std::get<1>(_nodes[_edges[edge_id].node].value);
    }

    void set_edge(EdgeId edge_id, const EdgeValue& edge_value) {
        check_edge(edge_id);
        set_edge_node_value(_edges[edge_id].node, edge_value);
    }

    EdgeId add_edge(VertexId u, VertexId v, const EdgeValue& edge_value) {
        check_vertex(u);
        check_vertex(v);
        if (u == v || connected(u, v)) return -1;
        EdgeValue value = edge_value;
        int edge_id = int(_edges.size());
        int node = add_edge_node(value);
        _edges.push_back(OriginalEdge{u, v, node, true});
        bool ok1 = link_nodes(vertex_node(u), node);
        bool ok2 = link_nodes(node, vertex_node(v));
        assert(ok1 && ok2);
        return edge_id;
    }

    bool cut_edge(EdgeId edge_id) {
        check_edge(edge_id);
        OriginalEdge& edge = _edges[edge_id];
        if (!edge.alive) return false;
        bool ok1 = cut_nodes(vertex_node(edge.u), edge.node);
        bool ok2 = cut_nodes(edge.node, vertex_node(edge.v));
        if (ok1 && ok2) edge.alive = false;
        return ok1 && ok2;
    }

    void reroot(VertexId vertex) {
        evert_node(vertex_node(vertex));
    }

    bool connected(VertexId u, VertexId v) {
        check_vertex(u);
        check_vertex(v);
        return connected_nodes(vertex_node(u), vertex_node(v));
    }

    // Reroots the represented tree at vertex and returns its whole-tree cluster.
    Path component_prod(VertexId vertex) {
        int node = vertex_node(vertex);
        evert_node(node);
        return _nodes[node].prod;
    }

    Path query_component(VertexId vertex) {
        return component_prod(vertex);
    }
};

}  // namespace ds
}  // namespace m1une

#endif  // M1UNE_RAKE_COMPRESS_LINK_CUT_TREE_HPP
#line 1 "ds/dynamic_tree/rake_compress_link_cut_tree.hpp"



#include <cassert>
#include <utility>
#include <variant>
#include <vector>

namespace m1une {
namespace ds {

// Maintains a dynamic forest whose tree DP uses two different aggregate types.
// Point is a commutative group for virtual children, while Path is an ordered
// preferred-path cluster and does not need an inverse.
template <class TreeDPInfo>
struct RakeCompressLinkCutTree {
    using Point = typename TreeDPInfo::Point;
    using Path = typename TreeDPInfo::Path;
    using VertexValue = typename TreeDPInfo::VertexValue;
    using EdgeValue = typename TreeDPInfo::EdgeValue;
    using VertexId = int;
    using EdgeId = int;

   private:
    struct Node {
        int left = -1;
        int right = -1;
        int parent = -1;
        bool rev = false;
        std::variant<VertexValue, EdgeValue> value;
        Point virtual_prod;
        Path prod;
        Path rev_prod;

        explicit Node(const VertexValue& vertex_value)
            : value(std::in_place_index<0>, vertex_value),
              virtual_prod(Point::id()),
              prod(TreeDPInfo::make_vertex_path(virtual_prod, vertex_value)),
              rev_prod(prod) {}

        explicit Node(std::in_place_index_t<1>, const EdgeValue& edge_value)
            : value(std::in_place_index<1>, edge_value),
              virtual_prod(Point::id()),
              prod(TreeDPInfo::make_edge_path(virtual_prod, edge_value)),
              rev_prod(prod) {}
    };

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

    std::vector<Node> _nodes;
    std::vector<int> _vertex_nodes;
    std::vector<OriginalEdge> _edges;
    std::vector<int> _path_buffer;

    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];
        Path self = x.value.index() == 0
            ? TreeDPInfo::make_vertex_path(x.virtual_prod, std::get<0>(x.value))
            : TreeDPInfo::make_edge_path(x.virtual_prod, std::get<1>(x.value));
        x.prod = self;
        x.rev_prod = self;

        if (x.left != -1) {
            x.prod = TreeDPInfo::compress(_nodes[x.left].prod, x.prod);
            x.rev_prod = TreeDPInfo::compress(x.rev_prod, _nodes[x.left].rev_prod);
        }
        if (x.right != -1) {
            x.prod = TreeDPInfo::compress(x.prod, _nodes[x.right].prod);
            x.rev_prod = TreeDPInfo::compress(_nodes[x.right].rev_prod, x.rev_prod);
        }
    }

    void add_virtual_child(int node, int child) {
        if (child == -1) return;
        Point contribution = TreeDPInfo::to_point(_nodes[child].prod);
        _nodes[node].virtual_prod = TreeDPInfo::rake(_nodes[node].virtual_prod, contribution);
    }

    void remove_virtual_child(int node, int child) {
        if (child == -1) return;
        Point contribution = TreeDPInfo::to_point(_nodes[child].prod);
        _nodes[node].virtual_prod = TreeDPInfo::rake(_nodes[node].virtual_prod, contribution.inv());
    }

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

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

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

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

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

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

        update(parent);
        update(node);
    }

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

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

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

    void check_vertex(VertexId vertex) const {
        assert(0 <= vertex && vertex < int(_vertex_nodes.size()));
    }

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

    int vertex_node(VertexId vertex) const {
        check_vertex(vertex);
        return _vertex_nodes[vertex];
    }

    int add_edge_node(const EdgeValue& edge_value) {
        _nodes.emplace_back(std::in_place_index<1>, edge_value);
        return int(_nodes.size()) - 1;
    }

    void set_vertex_node_value(int node, const VertexValue& vertex_value) {
        check_node(node);
        access(node);
        _nodes[node].value.template emplace<0>(vertex_value);
        update(node);
    }

    void set_edge_node_value(int node, const EdgeValue& edge_value) {
        check_node(node);
        access(node);
        _nodes[node].value.template emplace<1>(edge_value);
        update(node);
    }

    void evert_node(int node) {
        check_node(node);
        access(node);
        apply_reverse(node);
    }

    int component_root_node(int node) {
        check_node(node);
        access(node);
        int cur = node;
        push(cur);
        while (_nodes[cur].left != -1) {
            cur = _nodes[cur].left;
            push(cur);
        }
        splay(cur);
        return cur;
    }

    bool connected_nodes(int u, int v) {
        if (u == v) return true;
        return component_root_node(u) == component_root_node(v);
    }

    bool link_nodes(int u, int v) {
        check_node(u);
        check_node(v);
        if (u == v) return false;
        evert_node(u);
        if (component_root_node(v) == u) return false;
        access(v);
        _nodes[u].parent = v;
        add_virtual_child(v, u);
        update(v);
        return true;
    }

    bool cut_nodes(int u, int v) {
        check_node(u);
        check_node(v);
        if (u == v) return false;
        evert_node(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;
    }

   public:
    RakeCompressLinkCutTree() = default;

    explicit RakeCompressLinkCutTree(const std::vector<VertexValue>& values) {
        _nodes.reserve(values.size());
        _vertex_nodes.reserve(values.size());
        for (const VertexValue& value : values) add_vertex(value);
    }

    int vertex_count() const {
        return int(_vertex_nodes.size());
    }

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

    VertexId add_vertex(const VertexValue& vertex_value) {
        VertexValue value = vertex_value;
        int node = int(_nodes.size());
        _nodes.emplace_back(value);
        _vertex_nodes.push_back(node);
        return int(_vertex_nodes.size()) - 1;
    }

    const VertexValue& get_vertex(VertexId vertex) const {
        return std::get<0>(_nodes[vertex_node(vertex)].value);
    }

    void set_vertex(VertexId vertex, const VertexValue& vertex_value) {
        set_vertex_node_value(vertex_node(vertex), vertex_value);
    }

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

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

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

    const EdgeValue& get_edge(EdgeId edge_id) const {
        check_edge(edge_id);
        return std::get<1>(_nodes[_edges[edge_id].node].value);
    }

    void set_edge(EdgeId edge_id, const EdgeValue& edge_value) {
        check_edge(edge_id);
        set_edge_node_value(_edges[edge_id].node, edge_value);
    }

    EdgeId add_edge(VertexId u, VertexId v, const EdgeValue& edge_value) {
        check_vertex(u);
        check_vertex(v);
        if (u == v || connected(u, v)) return -1;
        EdgeValue value = edge_value;
        int edge_id = int(_edges.size());
        int node = add_edge_node(value);
        _edges.push_back(OriginalEdge{u, v, node, true});
        bool ok1 = link_nodes(vertex_node(u), node);
        bool ok2 = link_nodes(node, vertex_node(v));
        assert(ok1 && ok2);
        return edge_id;
    }

    bool cut_edge(EdgeId edge_id) {
        check_edge(edge_id);
        OriginalEdge& edge = _edges[edge_id];
        if (!edge.alive) return false;
        bool ok1 = cut_nodes(vertex_node(edge.u), edge.node);
        bool ok2 = cut_nodes(edge.node, vertex_node(edge.v));
        if (ok1 && ok2) edge.alive = false;
        return ok1 && ok2;
    }

    void reroot(VertexId vertex) {
        evert_node(vertex_node(vertex));
    }

    bool connected(VertexId u, VertexId v) {
        check_vertex(u);
        check_vertex(v);
        return connected_nodes(vertex_node(u), vertex_node(v));
    }

    // Reroots the represented tree at vertex and returns its whole-tree cluster.
    Path component_prod(VertexId vertex) {
        int node = vertex_node(vertex);
        evert_node(node);
        return _nodes[node].prod;
    }

    Path query_component(VertexId vertex) {
        return component_prod(vertex);
    }
};

}  // namespace ds
}  // namespace m1une
Back to top page