Rerooting Static Top Tree
(graph/tree/rerooting_static_top_tree.hpp)

View this file on GitHub
Last update: 2026-08-13 01:41:40+09:00
Include: #include "graph/tree/rerooting_static_top_tree.hpp"

Overview

m1une::tree::RerootingStaticTopTree is the bidirectional cluster engine used for static-top-tree solutions to dynamic rerooting DP problems.

Compared with StaticTopTree, it stores each path cluster in both directions:

path_down: the cluster viewed from the ancestor-side boundary toward the descendant-side boundary.
path_up: the same cluster viewed from the descendant-side boundary toward the ancestor-side boundary.

This is the extra information needed when a query asks for the DP value with an arbitrary vertex v as the root. After removing v, the remaining connected components can be represented by $O(\log N)$ static-top-tree clusters. Some of those clusters are viewed in the original rooted direction, and some are viewed in the reverse direction. Therefore forward and backward transitions are kept separate.

This header maintains the decomposition and the cached directional cluster values under vertex-value and edge-cost updates. It also exposes the $O(\log N)$ rerooting walk around a query vertex with for_each_rerooting_step(v, f) and rerooting_steps(v).

There is deliberately no universal prod(v) member. For many static-top-tree applications, Path is not just a plain subtree DP value; it may be a directional transformation, a small automaton, or another problem-specific object. The library therefore supplies the ordered clusters needed to reroot at v, while your DP code decides how those clusters are folded and how the final answer is read.

Cluster Types

The structure uses three user-facing types:

Type	Meaning
`Vertex`	Stored value of one original vertex.
`Path`	A connected cluster with two boundary vertices on one heavy path.
`Point`	A collection of completed side components attached to one boundary vertex.

A Path cluster has an original orientation: top boundary first, bottom boundary second. In the rooted tree, the top boundary is closer to root.

For one path cluster:

path_down means “view the cluster starting from the top boundary”.
path_up means “view the cluster starting from the bottom boundary”.

A Point cluster has only one boundary vertex, so it does not have a down/up pair. It is the aggregate contribution of several independent components attached to that one boundary.

Operations

The constructor receives:

RerootingStaticTopTree(
    g,
    values,
    point_id,
    compress_down,
    compress_up,
    rake,
    add_edge_down,
    add_edge_up,
    add_vertex,
    root
);

The callbacks are:

Callback	Signature	Meaning
`compress_down`	`Path compress_down(Path upper, Path lower, Edge e)`	Concatenate two adjacent path clusters in the rooted direction. `e` goes from `upper`’s bottom boundary to `lower`’s top boundary.
`compress_up`	`Path compress_up(Path lower, Path upper, Edge e)`	Concatenate the same two clusters in reverse. `e` goes from `lower`’s top boundary to `upper`’s bottom boundary, usually `reverse_edge(original_e)`.
`rake`	`Point rake(Point a, Point b)`	Merge two independent point clusters attached to the same boundary vertex.
`add_edge_down`	`Point add_edge_down(Path child, Edge e)`	Convert a child path into a point contribution viewed from the parent side. `e.from` is the parent-side boundary and `e.to` is the path top boundary.
`add_edge_up`	`Point add_edge_up(Path parent_side, Edge e)`	Convert a path into a point contribution viewed from the child side. `e.from` is the child-side boundary and `e.to` is the path bottom boundary.
`add_vertex`	`Path add_vertex(Point side, Vertex value, int v)`	Insert original vertex `v` and its side contributions, making a one-vertex path.

point_id is the identity for rake.

In code examples, const auto& e is just a generic-lambda shorthand for the edge type m1une::graph::Edge<T>. You can spell it explicitly, for example const m1une::graph::Edge<long long>& e, if the graph cost type is long long.

The important detail is that compress_up and add_edge_up are not just aliases for the downward functions. They receive the path states in the opposite order and receive an edge whose direction is also opposite. If your DP stores direction-sensitive data, such as prefix/suffix values, hashes, affine functions, or ordered endpoint states, the backward formulas are often different from the forward formulas.

For a symmetric DP, the code may look almost the same, but it is still safer to write the two callbacks separately:

auto compress_down = [](Path upper, Path lower, const auto& e) {
    // Start from upper's top boundary, traverse upper downward,
    // cross e, then traverse lower downward.
};
auto compress_up = [](Path lower, Path upper, const auto& e) {
    // Start from lower's bottom boundary, traverse lower upward,
    // cross e, then traverse upper upward.
};

What Is Stored

Internally the structure is a binary expression tree. Each expression node is one of:

Node type	Output	Stored value
`AddVertex`	`Path`	`path_down` and `path_up` for one original vertex plus its raked side components.
`AddEdge`	`Point`	A child path converted through one rooted tree edge.
`Rake`	`Point`	The rake of two point clusters at the same boundary.
`Compress`	`Path`	The concatenation of two path clusters.

For a Compress node with left child upper, right child lower, and edge e from upper to lower, the cached values are:

path_down = compress_down(upper.path_down, lower.path_down, e);
path_up = compress_up(lower.path_up, upper.path_up, reverse_edge(e));

For an AddEdge node built from a rooted child edge e, the cached point is:

point = add_edge_down(child.path_down, e);

The upward edge conversion is not cached in AddEdge, because the rooted build only needs the downward side contribution. It is exposed as add_edge_up for rerooting query code that peels clusters from the opposite direction.

all_prod_down() is the whole tree viewed from root toward the bottom of the root heavy path. all_prod_up() is the same whole-tree cluster viewed from that bottom boundary back toward root. The bottom boundary is determined by the heavy paths chosen during construction; it is not an arbitrary query vertex.

Rerooting Steps

For a query vertex v, start with the original vertex node:

int cur = stt.vertex_node(v);
Point side = stt.local_point(v);

local_point(v) is the raked contribution of the non-heavy child components already stored inside the AddVertex node of v. If there are no such components, it returns point_id().

For low-level access, you can process the raw step stream:

stt.for_each_rerooting_step(v, [&](const auto& step) {
    using Step = decltype(stt)::step_type;
    if (step.type == Step::CompressLower) {
        // The current path cluster was the upper/left child.
        // step.sibling is the lower/right path cluster.
        // stt.path_down(step.sibling) is viewed from the current side.
    } else if (step.type == Step::CompressUpper) {
        // The current path cluster was the lower/right child.
        // step.sibling is the upper/left path cluster.
        // stt.path_up(step.sibling) is viewed from the current side.
    } else if (step.type == Step::AddEdge) {
        // Leaving a child path through step.edge.
        // step.edge is oriented parent -> child; reverse it when viewing upward.
    } else if (step.type == Step::RakeLeft) {
        // A point sibling before the current rake range.
    } else if (step.type == Step::RakeRight) {
        // A point sibling after the current rake range.
    } else {
        // Reached an AddVertex node. step.vertex is that original vertex.
    }
});

The same data can be materialized with rerooting_steps(v) if storing the walk is more convenient than visiting it online.

Each step has these fields:

Field	Meaning
`type`	One of `CompressLower`, `CompressUpper`, `AddEdge`, `RakeLeft`, `RakeRight`, `AddVertex`.
`node`	The expression-tree parent node reached by this step.
`sibling`	The sibling cluster for compress/rake steps, otherwise `-1`.
`vertex`	The original vertex for an `AddVertex` step, otherwise `-1`.
`edge`	The rooted tree edge for compress/add-edge steps.

This removes the error-prone part of rerooting queries: finding the sibling clusters and keeping their order straight. The folder you write for a problem only needs to say what each step means for that DP.

For ordinary use, prefer fold_rerooting(v, folder). It performs this dispatch for you and passes already-oriented cluster values to the folder. The effective folder method signatures are:

Folder method	Signature	Called when
`start`	`void start(int v, const Vertex& value, const Point& local_point)`	Before processing the walk from `v`.
`compress_lower`	`void compress_lower(const Path& path, Edge edge)`	A lower path sibling is attached below the current path.
`compress_upper`	`void compress_upper(const Path& path, Edge edge)`	An upper path sibling is attached above the current path.
`add_edge`	`void add_edge(Edge edge)`	The walk leaves a child path and moves toward its parent vertex.
`rake_left`	`void rake_left(const Point& point)`	A point sibling appears before the current rake range.
`rake_right`	`void rake_right(const Point& point)`	A point sibling appears after the current rake range.
`add_vertex`	`void add_vertex(int vertex, const Vertex& value)`	The walk reaches a parent `AddVertex` node.
`result`	`Answer result() const`	Returns the query answer after the walk.

Here Edge is the structure’s edge_type, and Answer is the return type of fold_rerooting. The methods may take small arguments by value instead of by const reference if that is more convenient.

Here compress_upper and add_edge receive reversed edges, so the edge is oriented in the direction the rerooting walk is moving.

Public Members

Method	Description	Complexity
`RerootingStaticTopTree(...)`	Builds the expression tree.	$O(N \log N)$ callback work
`int size()`	Number of original vertices.	$O(1)$
`bool empty()`	Whether the original tree is empty.	$O(1)$
`int root()`	Root used to orient the static decomposition.	$O(1)$
`int root_node()`	Expression-tree node id of the whole-tree path cluster.	$O(1)$
`int node_count()`	Number of expression-tree nodes.	$O(1)$
`int height()`	Height of the expression tree. Updates are proportional to this.	$O(1)$
`const std::vector<Node>& nodes()`	All expression-tree nodes.	$O(1)$
`const Node& node(id)`	One expression-tree node.	$O(1)$
`int parent_node(id)`	Parent expression node, or `-1` at the root.	$O(1)$
`int vertex_node(v)`	The `AddVertex` node corresponding to original vertex `v`.	$O(1)$
`int local_point_node(v)`	Rake node stored inside `AddVertex(v)`, or `-1`.	$O(1)$
`const Point& local_point(v)`	Raked non-heavy child contribution stored at `v`, or `point_id()`.	$O(1)$
`const Vertex& get(v)`	Stored value of original vertex `v`.	$O(1)$
`void set(v, value)`	Update one vertex value and recompute ancestors.	$O(\text{height})$
`void set_edge_cost(edge_id, cost)`	Update one edge cost and recompute ancestors.	$O(\text{height})$
`const Path& path_down(node_id)`	Downward path value of a path-output node.	$O(1)$
`const Path& path_up(node_id)`	Upward path value of a path-output node.	$O(1)$
`const Point& point(node_id)`	Point value of a point-output node.	$O(1)$
`const Path& all_prod_down()`	Whole-tree downward path value.	$O(1)$
`const Path& all_prod_up()`	Whole-tree upward path value.	$O(1)$
`const Point& point_id()`	Identity point value for `rake`.	$O(1)$
`for_each_rerooting_step(v, f)`	Visits rerooting steps from `vertex_node(v)` to `root_node()`.	$O(\text{height})$
`std::vector<RerootingStep> rerooting_steps(v)`	Returns the same rerooting steps as a vector.	$O(\text{height})$
`fold_rerooting(v, folder)`	Runs the rerooting walk and calls the folder methods above.	$O(\text{height})$
`compress_down(...)`, `compress_up(...)`	Public wrappers around the directional path callbacks.	Callback cost
`rake(...)`	Public wrapper around the point merge callback.	Callback cost
`add_edge_down(...)`, `add_edge_up(...)`	Public wrappers around the directional edge callbacks.	Callback cost
`add_vertex(...)`	Public wrapper around the vertex callback.	Callback cost
`static reverse_edge(edge)`	Returns a copy of `edge` with `from` and `to` swapped.	$O(1)$

Calling path_down or path_up on a point-output node, or point on a path-output node, is a logic error and is checked by assert.

Using It In Problems

For a rerooting-style static top tree solution:

Define Point as the DP aggregate for independent neighbor components attached to one vertex.
Define Path as the information needed to move that aggregate through a chain of vertices in both directions.
Implement the downward operations exactly as in an ordinary static top tree.
Implement the upward operations with the reverse argument order and reversed edge direction.
For a query vertex v, initialize the query state from local_point(v), then process for_each_rerooting_step(v, f). The siblings encountered on this walk form the $O(\log N)$ clusters needed for the rerooted answer.

The final fold depends on the DP. For example, a DP that stores path clusters as functions usually applies the collected functions to a point state; a DP that stores endpoint states may keep separate accumulators for the parent side and child side before the final add_vertex. In problems such as ABC460 G, the folder keeps the same-color component contribution around the query vertex and reads the component sum after applying the steps.

Example: ABC460 G - Vertex Flip Query

ABC460 G asks for dynamic updates on a colored, weighted tree:

flip one vertex color,
add to one vertex weight,
for a vertex v, output the sum of weights in the connected component of v after deleting all vertices whose color differs from color[v].

This can be seen as a rerooting DP query. If the tree is rooted at v, the answer is the contribution of all neighbor-side components that can connect to v through vertices of the same color.

One convenient state is:

struct Vertex {
    long long weight;
    int color;
};

struct Point {
    long long sum[2];
};

struct Path {
    int first_color, last_color;
    long long first_sum, last_sum;
    bool connected;
};

The meaning is:

State	Meaning
`Point::sum[c]`	For side components attached to a boundary vertex, total contribution reachable if the boundary vertex has color `c`.
`Path::first_color`	Color of the first boundary in the current orientation.
`Path::last_color`	Color of the last boundary in the current orientation.
`Path::first_sum`	Same-color component sum containing the first boundary, inside this path cluster.
`Path::last_sum`	Same-color component sum containing the last boundary, inside this path cluster.
`Path::connected`	Whether the first and last boundaries are in the same same-color component.

The cluster operations are short:

auto compress = [](Path a, Path b, const auto&) {
    bool join = a.last_color == b.first_color;
    Path res{a.first_color, b.last_color, a.first_sum, b.last_sum, false};
    if (join && a.connected) res.first_sum += b.first_sum;
    if (join && b.connected) res.last_sum += a.last_sum;
    res.connected = a.connected && b.connected && join;
    return res;
};

auto rake = [](Point a, Point b) {
    return Point{a.sum[0] + b.sum[0], a.sum[1] + b.sum[1]};
};

auto add_edge = [](Path path, const auto&) {
    Point res{};
    res.sum[path.first_color] = path.first_sum;
    return res;
};

auto add_vertex = [](Point side, Vertex value, int) {
    long long sum = value.weight + side.sum[value.color];
    return Path{value.color, value.color, sum, sum, true};
};

Here compress is orientation-relative, so it can be used for both compress_down and compress_up. Likewise add_edge can be used for both edge directions because the graph edge itself does not change the component value; only endpoint colors decide whether the component can pass through the next vertex.

Build the structure like this:

auto stt = m1une::tree::RerootingStaticTopTree(
    g,
    values,
    Point{0, 0},
    compress,
    compress,
    rake,
    add_edge,
    add_edge,
    add_vertex
);

For query type 3 v, define a folder and pass it to fold_rerooting. The folder keeps the component containing the original query vertex and grows it while the library climbs from vertex_node(v) to the expression root.

using Stt = decltype(stt);

struct QueryFolder {
    const Stt& stt;
    int color = 0;
    long long answer = 0;
    bool touches_top = false;
    bool touches_bottom = false;
    bool pending_open = false;
    Point pending{};

    void start(int, const Vertex& value, const Point& local) {
        color = value.color;
        answer = value.weight + local.sum[color];
        touches_top = true;
        touches_bottom = true;
        pending_open = false;
        pending = stt.point_id();
    }

    void compress_lower(const Path& lower, Stt::edge_type) {
        bool connect = touches_bottom && lower.first_color == color;
        if (connect) answer += lower.first_sum;
        touches_bottom = connect && lower.connected;
    }

    void compress_upper(const Path& upper, Stt::edge_type) {
        bool connect = touches_top && upper.first_color == color;
        if (connect) answer += upper.first_sum;
        touches_top = connect && upper.connected;
    }

    void add_edge(Stt::edge_type) {
        pending_open = touches_top;
        pending = stt.point_id();
    }

    void rake_left(const Point& point) {
        if (pending_open) pending = stt.rake(point, pending);
    }

    void rake_right(const Point& point) {
        if (pending_open) pending = stt.rake(pending, point);
    }

    void add_vertex(int, const Vertex& value) {
        if (pending_open && value.color == color) {
            answer += value.weight + pending.sum[color];
            touches_top = true;
            touches_bottom = true;
        } else {
            touches_top = false;
            touches_bottom = false;
        }
        pending_open = false;
        pending = stt.point_id();
    }

    long long result() const {
        return answer;
    }
};

auto query = [&](int v) {
    return stt.fold_rerooting(v, QueryFolder{stt});
};

The flags have these roles:

Variable	Meaning
`touches_top`	The query component reaches the current path cluster’s top boundary.
`touches_bottom`	The query component reaches the current path cluster’s bottom boundary.
`pending_open`	We have moved from a child path into a parent-side point/rake cluster, and the component can still reach the parent vertex.
`pending`	Other side components of that parent vertex collected while climbing through `Rake` nodes.

For updates, keep the external values array in sync and call set:

// type 1: flip color
values[v].color ^= 1;
stt.set(v, values[v]);

// type 2: add weight
values[v].weight += x;
stt.set(v, values[v]);

// type 3: answer
std::cout << query(v) << '\n';

The input vertices in ABC460 G are 1-indexed, so decrement v before using these snippets.

The total complexity is $O(N \log N)$ construction callback work and $O(\log N)$ per update/query, assuming the static top tree height is logarithmic. The verification test test_rerooting_static_top_tree_vertex_component contains a small brute-force-checked version of this pattern.

The library guarantees that the cluster values you read during that fold are kept up to date after set and set_edge_cost.

Example: Directional Distance Aggregates

This example stores, for a path cluster:

count: number of vertices in the cluster.
sum: sum of distances from the current viewing boundary.
length: distance between the two path boundaries.

The downward and upward formulas have the same shape for distances, but the argument names and edge direction are intentionally different.

struct Path {
    long long count;
    long long sum;
    long long length;
};

struct Point {
    long long count;
    long long sum;
};

auto compress_down = [](Path upper, Path lower, const auto& e) {
    long long shift = upper.length + e.cost;
    return Path{
        upper.count + lower.count,
        upper.sum + lower.sum + lower.count * shift,
        upper.length + e.cost + lower.length
    };
};

auto compress_up = [](Path lower, Path upper, const auto& e) {
    long long shift = lower.length + e.cost;
    return Path{
        lower.count + upper.count,
        lower.sum + upper.sum + upper.count * shift,
        lower.length + e.cost + upper.length
    };
};

auto rake = [](Point a, Point b) {
    return Point{a.count + b.count, a.sum + b.sum};
};

auto add_edge_down = [](Path child, const auto& e) {
    return Point{child.count, child.sum + child.count * e.cost};
};

auto add_edge_up = [](Path parent_side, const auto& e) {
    return Point{parent_side.count, parent_side.sum + parent_side.count * e.cost};
};

auto add_vertex = [](Point side, long long weight, int) {
    return Path{side.count + weight, side.sum, 0};
};

auto stt = m1une::tree::RerootingStaticTopTree(
    g,
    weights,
    Point{0, 0},
    compress_down,
    compress_up,
    rake,
    add_edge_down,
    add_edge_up,
    add_vertex
);

For this DP, stt.all_prod_down().sum is the sum of distances from the build root to all weighted vertices. stt.all_prod_up().sum is the sum of distances from the bottom boundary of the root heavy path to all weighted vertices.

Notes

The input graph should be an undirected connected tree built with add_edge. Inactive edges are ignored during construction.

If the tree topology or the build root changes, rebuild the structure. Vertex values and edge costs can be updated with set and set_edge_cost.

Depends on

Graph (graph/graph.hpp)

Required by

Verified with

Code

#ifndef M1UNE_TREE_REROOTING_STATIC_TOP_TREE_HPP
#define M1UNE_TREE_REROOTING_STATIC_TOP_TREE_HPP 1

#include <algorithm>
#include <cassert>
#include <optional>
#include <type_traits>
#include <utility>
#include <vector>

#include "../graph.hpp"

namespace m1une {
namespace tree {

namespace internal {

enum class RerootingStaticTopTreeNodeType {
    Compress,
    Rake,
    AddEdge,
    AddVertex,
};

enum class RerootingStaticTopTreeStepType {
    CompressLower,
    CompressUpper,
    AddEdge,
    RakeLeft,
    RakeRight,
    AddVertex,
};

}  // namespace internal

template <class T, class Vertex, class Path, class Point, class CompressDown, class CompressUp, class Rake,
          class AddEdgeDown, class AddEdgeUp, class AddVertex>
struct RerootingStaticTopTree {
    using cost_type = T;
    using vertex_type = Vertex;
    using path_type = Path;
    using point_type = Point;
    using edge_type = m1une::graph::Edge<T>;
    using node_type = internal::RerootingStaticTopTreeNodeType;
    using step_type = internal::RerootingStaticTopTreeStepType;

    struct Node {
        node_type type;
        int left = -1;
        int right = -1;
        int parent = -1;
        int vertex = -1;
        edge_type edge;
        int size = 0;
        int height = 1;
        std::optional<Path> path_down;
        std::optional<Path> path_up;
        std::optional<Point> point;
    };

    struct RerootingStep {
        step_type type;
        int node = -1;
        int sibling = -1;
        int vertex = -1;
        edge_type edge;
    };

   private:
    int _n;
    int _root;
    int _root_node;
    Point _point_id;
    CompressDown _compress_down;
    CompressUp _compress_up;
    Rake _rake;
    AddEdgeDown _add_edge_down;
    AddEdgeUp _add_edge_up;
    AddVertex _add_vertex;
    std::vector<Vertex> _values;
    std::vector<Node> _nodes;
    std::vector<int> _vertex_node;
    std::vector<int> _edge_node;
    std::vector<int> _parent;
    std::vector<int> _subtree_size;
    std::vector<int> _heavy;
    std::vector<edge_type> _heavy_edge;
    std::vector<std::vector<edge_type>> _children;

    static edge_type reversed_edge(edge_type e) {
        std::swap(e.from, e.to);
        return e;
    }

    const Path& node_path_down(int node) const {
        assert(0 <= node && node < int(_nodes.size()));
        assert(_nodes[node].path_down.has_value());
        return *_nodes[node].path_down;
    }

    const Path& node_path_up(int node) const {
        assert(0 <= node && node < int(_nodes.size()));
        assert(_nodes[node].path_up.has_value());
        return *_nodes[node].path_up;
    }

    const Point& node_point(int node) const {
        assert(0 <= node && node < int(_nodes.size()));
        assert(_nodes[node].point.has_value());
        return *_nodes[node].point;
    }

    void set_parent(int child, int parent) {
        if (child != -1) _nodes[child].parent = parent;
    }

    void recompute(int node) {
        auto& x = _nodes[node];
        if (x.type == node_type::Compress) {
            x.path_down = _compress_down(node_path_down(x.left), node_path_down(x.right), x.edge);
            x.path_up = _compress_up(node_path_up(x.right), node_path_up(x.left), reversed_edge(x.edge));
        } else if (x.type == node_type::Rake) {
            x.point = _rake(node_point(x.left), node_point(x.right));
        } else if (x.type == node_type::AddEdge) {
            x.point = _add_edge_down(node_path_down(x.left), x.edge);
        } else {
            const Point& side = x.left == -1 ? _point_id : node_point(x.left);
            Path path = _add_vertex(side, _values[x.vertex], x.vertex);
            x.path_down = path;
            x.path_up = std::move(path);
        }
    }

    int new_node(Node node) {
        int id = int(_nodes.size());
        _nodes.push_back(std::move(node));
        set_parent(_nodes[id].left, id);
        set_parent(_nodes[id].right, id);
        recompute(id);
        return id;
    }

    int new_compress(int left, int right, edge_type edge) {
        Node node;
        node.type = node_type::Compress;
        node.left = left;
        node.right = right;
        node.edge = edge;
        node.size = _nodes[left].size + _nodes[right].size;
        node.height = std::max(_nodes[left].height, _nodes[right].height) + 1;
        int id = new_node(std::move(node));
        if (0 <= edge.id && edge.id < int(_edge_node.size())) _edge_node[edge.id] = id;
        return id;
    }

    int new_rake(int left, int right) {
        Node node;
        node.type = node_type::Rake;
        node.left = left;
        node.right = right;
        node.size = _nodes[left].size + _nodes[right].size;
        node.height = std::max(_nodes[left].height, _nodes[right].height) + 1;
        return new_node(std::move(node));
    }

    int new_add_edge(int child, edge_type edge) {
        Node node;
        node.type = node_type::AddEdge;
        node.left = child;
        node.edge = edge;
        node.size = _nodes[child].size;
        node.height = _nodes[child].height + 1;
        int id = new_node(std::move(node));
        if (0 <= edge.id && edge.id < int(_edge_node.size())) _edge_node[edge.id] = id;
        return id;
    }

    int new_add_vertex(int side, int vertex) {
        Node node;
        node.type = node_type::AddVertex;
        node.left = side;
        node.vertex = vertex;
        node.size = 1 + (side == -1 ? 0 : _nodes[side].size);
        node.height = 1 + (side == -1 ? 0 : _nodes[side].height);
        int id = new_node(std::move(node));
        _vertex_node[vertex] = id;
        return id;
    }

    int weighted_split(const std::vector<int>& nodes, int l, int r) const {
        int total = 0;
        for (int i = l; i < r; i++) total += _nodes[nodes[i]].size;
        int left_sum = 0;
        for (int i = l; i + 1 < r; i++) {
            left_sum += _nodes[nodes[i]].size;
            if (2 * left_sum >= total) return i + 1;
        }
        return r - 1;
    }

    int build_rake(const std::vector<int>& nodes, int l, int r) {
        if (l == r) return -1;
        if (l + 1 == r) return nodes[l];
        int m = weighted_split(nodes, l, r);
        return new_rake(build_rake(nodes, l, m), build_rake(nodes, m, r));
    }

    int build_compress(const std::vector<int>& nodes, const std::vector<edge_type>& edges, int l, int r) {
        if (l + 1 == r) return nodes[l];
        int m = weighted_split(nodes, l, r);
        return new_compress(build_compress(nodes, edges, l, m), build_compress(nodes, edges, m, r), edges[m - 1]);
    }

    int build_vertex(int v) {
        std::vector<int> side_nodes;
        for (const auto& e : _children[v]) {
            if (e.to == _heavy[v]) continue;
            int child_path = build_path(e.to);
            side_nodes.push_back(new_add_edge(child_path, e));
        }
        return new_add_vertex(build_rake(side_nodes, 0, int(side_nodes.size())), v);
    }

    int build_path(int start) {
        std::vector<int> path_nodes;
        std::vector<edge_type> path_edges;
        for (int v = start; v != -1; v = _heavy[v]) {
            path_nodes.push_back(build_vertex(v));
            if (_heavy[v] != -1) path_edges.push_back(_heavy_edge[v]);
        }
        return build_compress(path_nodes, path_edges, 0, int(path_nodes.size()));
    }

    void recompute_up(int node) {
        while (node != -1) {
            recompute(node);
            node = _nodes[node].parent;
        }
    }

   public:
    RerootingStaticTopTree(const m1une::graph::Graph<T>& g, const std::vector<Vertex>& values, Point point_id,
                           CompressDown compress_down, CompressUp compress_up, Rake rake,
                           AddEdgeDown add_edge_down, AddEdgeUp add_edge_up, AddVertex add_vertex, int root = 0)
        : _n(g.size()),
          _root(_n == 0 ? -1 : root),
          _root_node(-1),
          _point_id(std::move(point_id)),
          _compress_down(std::move(compress_down)),
          _compress_up(std::move(compress_up)),
          _rake(std::move(rake)),
          _add_edge_down(std::move(add_edge_down)),
          _add_edge_up(std::move(add_edge_up)),
          _add_vertex(std::move(add_vertex)),
          _values(values) {
        build(g, root);
    }

    void build(const m1une::graph::Graph<T>& g, int root = 0) {
        _n = g.size();
        _root = _n == 0 ? -1 : root;
        assert(int(_values.size()) == _n);
        _nodes.clear();
        _vertex_node.assign(_n, -1);
        _edge_node.assign(g.edge_count(), -1);
        _parent.assign(_n, -2);
        _subtree_size.assign(_n, 1);
        _heavy.assign(_n, -1);
        _heavy_edge.assign(_n, edge_type());
        _children.assign(_n, {});
        _root_node = -1;

        if (_n == 0) return;
        assert(0 <= root && root < _n);
        assert(int(g.edges().size()) == _n - 1);

        std::vector<int> order;
        order.reserve(_n);
        std::vector<int> stack = {root};
        _parent[root] = -1;
        while (!stack.empty()) {
            int v = stack.back();
            stack.pop_back();
            order.push_back(v);
            for (const auto& e : g[v]) {
                if (!e.alive) continue;
                if (_parent[e.to] != -2) continue;
                _parent[e.to] = v;
                _children[v].push_back(e);
                stack.push_back(e.to);
            }
        }
        assert(int(order.size()) == _n);

        for (int i = int(order.size()) - 1; i >= 0; i--) {
            int v = order[i];
            for (const auto& e : _children[v]) {
                _subtree_size[v] += _subtree_size[e.to];
                if (_heavy[v] == -1 || _subtree_size[_heavy[v]] < _subtree_size[e.to]) {
                    _heavy[v] = e.to;
                    _heavy_edge[v] = e;
                }
            }
        }

        _root_node = build_path(root);
    }

    int size() const {
        return _n;
    }

    bool empty() const {
        return _n == 0;
    }

    int root() const {
        return _root;
    }

    int root_node() const {
        return _root_node;
    }

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

    int height() const {
        return _root_node == -1 ? 0 : _nodes[_root_node].height;
    }

    const std::vector<Node>& nodes() const {
        return _nodes;
    }

    const Node& node(int id) const {
        assert(0 <= id && id < int(_nodes.size()));
        return _nodes[id];
    }

    int parent_node(int id) const {
        return node(id).parent;
    }

    int vertex_node(int v) const {
        assert(0 <= v && v < _n);
        return _vertex_node[v];
    }

    int local_point_node(int v) const {
        int id = vertex_node(v);
        assert(_nodes[id].type == node_type::AddVertex);
        return _nodes[id].left;
    }

    const Point& local_point(int v) const {
        int point_node = local_point_node(v);
        return point_node == -1 ? _point_id : node_point(point_node);
    }

    const Vertex& get(int v) const {
        assert(0 <= v && v < _n);
        return _values[v];
    }

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

    void set(int v, const Vertex& value) {
        assert(0 <= v && v < _n);
        assert(_vertex_node[v] != -1);
        _values[v] = value;
        recompute_up(_vertex_node[v]);
    }

    void set(int v, Vertex&& value) {
        assert(0 <= v && v < _n);
        assert(_vertex_node[v] != -1);
        _values[v] = std::move(value);
        recompute_up(_vertex_node[v]);
    }

    void set_edge_cost(int edge_id, T cost) {
        assert(0 <= edge_id && edge_id < int(_edge_node.size()));
        int node = _edge_node[edge_id];
        assert(node != -1);
        _nodes[node].edge.cost = cost;
        recompute_up(node);
    }

    const Path& path_down(int node_id) const {
        return node_path_down(node_id);
    }

    const Path& path_up(int node_id) const {
        return node_path_up(node_id);
    }

    const Point& point(int node_id) const {
        return node_point(node_id);
    }

    const Path& all_prod_down() const {
        assert(_root_node != -1);
        return path_down(_root_node);
    }

    const Path& all_prod_up() const {
        assert(_root_node != -1);
        return path_up(_root_node);
    }

    const Point& point_id() const {
        return _point_id;
    }

    template <class F>
    void for_each_rerooting_step(int v, F&& f) const {
        assert(0 <= v && v < _n);
        int cur = _vertex_node[v];
        assert(cur != -1);
        while (_nodes[cur].parent != -1) {
            int par = _nodes[cur].parent;
            const auto& p = _nodes[par];
            RerootingStep step;
            step.node = par;
            if (p.type == node_type::Compress) {
                step.edge = p.edge;
                if (p.left == cur) {
                    step.type = step_type::CompressLower;
                    step.sibling = p.right;
                } else {
                    assert(p.right == cur);
                    step.type = step_type::CompressUpper;
                    step.sibling = p.left;
                }
            } else if (p.type == node_type::Rake) {
                if (p.left == cur) {
                    step.type = step_type::RakeRight;
                    step.sibling = p.right;
                } else {
                    assert(p.right == cur);
                    step.type = step_type::RakeLeft;
                    step.sibling = p.left;
                }
            } else if (p.type == node_type::AddEdge) {
                assert(p.left == cur);
                step.type = step_type::AddEdge;
                step.edge = p.edge;
            } else {
                assert(p.type == node_type::AddVertex);
                assert(p.left == cur);
                step.type = step_type::AddVertex;
                step.vertex = p.vertex;
            }
            f(step);
            cur = par;
        }
    }

    std::vector<RerootingStep> rerooting_steps(int v) const {
        std::vector<RerootingStep> result;
        int cur = vertex_node(v);
        int depth = 0;
        while (_nodes[cur].parent != -1) {
            cur = _nodes[cur].parent;
            depth++;
        }
        result.reserve(depth);
        for_each_rerooting_step(v, [&](const RerootingStep& step) {
            result.push_back(step);
        });
        return result;
    }

    template <class Folder>
    auto fold_rerooting(int v, Folder folder) const {
        folder.start(v, _values[v], local_point(v));
        for_each_rerooting_step(v, [&](const RerootingStep& step) {
            if (step.type == step_type::CompressLower) {
                folder.compress_lower(path_down(step.sibling), step.edge);
            } else if (step.type == step_type::CompressUpper) {
                folder.compress_upper(path_up(step.sibling), reversed_edge(step.edge));
            } else if (step.type == step_type::AddEdge) {
                folder.add_edge(reversed_edge(step.edge));
            } else if (step.type == step_type::RakeLeft) {
                folder.rake_left(point(step.sibling));
            } else if (step.type == step_type::RakeRight) {
                folder.rake_right(point(step.sibling));
            } else {
                folder.add_vertex(step.vertex, _values[step.vertex]);
            }
        });
        return folder.result();
    }

    Path compress_down(const Path& upper, const Path& lower, edge_type edge) const {
        return _compress_down(upper, lower, edge);
    }

    Path compress_up(const Path& lower, const Path& upper, edge_type edge) const {
        return _compress_up(lower, upper, edge);
    }

    Point rake(const Point& left, const Point& right) const {
        return _rake(left, right);
    }

    Point add_edge_down(const Path& path, edge_type edge) const {
        return _add_edge_down(path, edge);
    }

    Point add_edge_up(const Path& path, edge_type edge) const {
        return _add_edge_up(path, edge);
    }

    Path add_vertex(const Point& side, const Vertex& value, int vertex) const {
        return _add_vertex(side, value, vertex);
    }

    static edge_type reverse_edge(edge_type edge) {
        return reversed_edge(edge);
    }
};

template <class T, class Vertex, class Point, class CompressDown, class CompressUp, class Rake, class AddEdgeDown,
          class AddEdgeUp, class AddVertex>
RerootingStaticTopTree(const m1une::graph::Graph<T>&, const std::vector<Vertex>&, Point, CompressDown, CompressUp,
                       Rake, AddEdgeDown, AddEdgeUp, AddVertex, int)
    -> RerootingStaticTopTree<T, Vertex, std::invoke_result_t<AddVertex, Point, Vertex, int>, Point, CompressDown,
                              CompressUp, Rake, AddEdgeDown, AddEdgeUp, AddVertex>;

template <class T, class Vertex, class Point, class CompressDown, class CompressUp, class Rake, class AddEdgeDown,
          class AddEdgeUp, class AddVertex>
RerootingStaticTopTree(const m1une::graph::Graph<T>&, const std::vector<Vertex>&, Point, CompressDown, CompressUp,
                       Rake, AddEdgeDown, AddEdgeUp, AddVertex)
    -> RerootingStaticTopTree<T, Vertex, std::invoke_result_t<AddVertex, Point, Vertex, int>, Point, CompressDown,
                              CompressUp, Rake, AddEdgeDown, AddEdgeUp, AddVertex>;

}  // namespace tree
}  // namespace m1une

#endif  // M1UNE_TREE_REROOTING_STATIC_TOP_TREE_HPP

#line 1 "graph/tree/rerooting_static_top_tree.hpp"



#include <algorithm>
#include <cassert>
#include <optional>
#include <type_traits>
#include <utility>
#include <vector>

#line 1 "graph/graph.hpp"



#include <array>
#line 8 "graph/graph.hpp"

namespace m1une {
namespace graph {

template <class T = int>
struct Edge {
    using cost_type = T;

    int from;
    int to;
    T cost;
    int id;
    bool alive;

    Edge() : from(-1), to(-1), cost(T()), id(-1), alive(true) {}
    Edge(int from_, int to_, T cost_ = T(1), int id_ = -1, bool alive_ = true)
        : from(from_), to(to_), cost(cost_), id(id_), alive(alive_) {}

    int other(int v) const {
        assert(v == from || v == to);
        return from ^ to ^ v;
    }
};

template <class T = int>
struct Graph {
    using edge_type = Edge<T>;
    using cost_type = T;

   private:
    struct EdgePositions {
        std::array<std::pair<int, int>, 2> value{};
        int size = 0;

        void push_back(std::pair<int, int> position) {
            assert(size < 2);
            value[size++] = position;
        }
    };

    int _n;
    int _edge_count;
    std::vector<std::vector<edge_type>> _g;
    std::vector<EdgePositions> _edge_positions;

   public:
    Graph() : _n(0), _edge_count(0) {}
    explicit Graph(int n) : _n(n), _edge_count(0), _g(n) {
        assert(0 <= n);
    }

    int size() const {
        return _n;
    }

    bool empty() const {
        return _n == 0;
    }

    int edge_count() const {
        return _edge_count;
    }

    int add_vertex() {
        _g.emplace_back();
        return _n++;
    }

    int add_directed_edge(int from, int to, T cost = T(1)) {
        assert(0 <= from && from < _n);
        assert(0 <= to && to < _n);
        int id = _edge_count++;
        int idx = int(_g[from].size());
        _g[from].push_back(edge_type(from, to, cost, id));
        _edge_positions.emplace_back();
        _edge_positions.back().push_back({from, idx});
        return id;
    }

    int add_edge(int u, int v, T cost = T(1)) {
        assert(0 <= u && u < _n);
        assert(0 <= v && v < _n);
        int id = _edge_count++;
        int u_idx = int(_g[u].size());
        _g[u].push_back(edge_type(u, v, cost, id));
        int v_idx = int(_g[v].size());
        _g[v].push_back(edge_type(v, u, cost, id));
        _edge_positions.emplace_back();
        _edge_positions.back().push_back({u, u_idx});
        _edge_positions.back().push_back({v, v_idx});
        return id;
    }

    void set_edge_alive(int id, bool alive) {
        assert(0 <= id && id < _edge_count);
        for (int i = 0; i < _edge_positions[id].size; ++i) {
            auto [v, idx] = _edge_positions[id].value[i];
            _g[v][idx].alive = alive;
        }
    }

    void erase_edge(int id) {
        set_edge_alive(id, false);
    }

    void revive_edge(int id) {
        set_edge_alive(id, true);
    }

    bool is_edge_alive(int id) const {
        assert(0 <= id && id < _edge_count);
        assert(_edge_positions[id].size != 0);
        auto [v, idx] = _edge_positions[id].value[0];
        return _g[v][idx].alive;
    }

    const std::vector<edge_type>& operator[](int v) const {
        assert(0 <= v && v < _n);
        return _g[v];
    }

    std::vector<edge_type>& operator[](int v) {
        assert(0 <= v && v < _n);
        return _g[v];
    }

    const std::vector<std::vector<edge_type>>& adjacency() const {
        return _g;
    }

    std::vector<std::vector<edge_type>>& adjacency() {
        return _g;
    }

    std::vector<edge_type> edges(bool include_inactive = false) const {
        std::vector<edge_type> result;
        result.reserve(_edge_count);
        std::vector<char> used(_edge_count, false);
        for (int v = 0; v < _n; v++) {
            for (const auto& e : _g[v]) {
                if (!include_inactive && !e.alive) continue;
                if (0 <= e.id && e.id < _edge_count) {
                    if (used[e.id]) continue;
                    used[e.id] = true;
                }
                result.push_back(e);
            }
        }
        return result;
    }

    Graph reversed() const {
        Graph result(_n);
        result._edge_count = _edge_count;
        result._edge_positions.assign(_edge_count, {});
        for (int v = 0; v < _n; v++) {
            for (const auto& e : _g[v]) {
                int idx = int(result._g[e.to].size());
                result._g[e.to].push_back(edge_type(e.to, e.from, e.cost, e.id, e.alive));
                if (0 <= e.id && e.id < _edge_count) result._edge_positions[e.id].push_back({e.to, idx});
            }
        }
        return result;
    }
};

}  // namespace graph
}  // namespace m1une


#line 12 "graph/tree/rerooting_static_top_tree.hpp"

namespace m1une {
namespace tree {

namespace internal {

enum class RerootingStaticTopTreeNodeType {
    Compress,
    Rake,
    AddEdge,
    AddVertex,
};

enum class RerootingStaticTopTreeStepType {
    CompressLower,
    CompressUpper,
    AddEdge,
    RakeLeft,
    RakeRight,
    AddVertex,
};

}  // namespace internal

template <class T, class Vertex, class Path, class Point, class CompressDown, class CompressUp, class Rake,
          class AddEdgeDown, class AddEdgeUp, class AddVertex>
struct RerootingStaticTopTree {
    using cost_type = T;
    using vertex_type = Vertex;
    using path_type = Path;
    using point_type = Point;
    using edge_type = m1une::graph::Edge<T>;
    using node_type = internal::RerootingStaticTopTreeNodeType;
    using step_type = internal::RerootingStaticTopTreeStepType;

    struct Node {
        node_type type;
        int left = -1;
        int right = -1;
        int parent = -1;
        int vertex = -1;
        edge_type edge;
        int size = 0;
        int height = 1;
        std::optional<Path> path_down;
        std::optional<Path> path_up;
        std::optional<Point> point;
    };

    struct RerootingStep {
        step_type type;
        int node = -1;
        int sibling = -1;
        int vertex = -1;
        edge_type edge;
    };

   private:
    int _n;
    int _root;
    int _root_node;
    Point _point_id;
    CompressDown _compress_down;
    CompressUp _compress_up;
    Rake _rake;
    AddEdgeDown _add_edge_down;
    AddEdgeUp _add_edge_up;
    AddVertex _add_vertex;
    std::vector<Vertex> _values;
    std::vector<Node> _nodes;
    std::vector<int> _vertex_node;
    std::vector<int> _edge_node;
    std::vector<int> _parent;
    std::vector<int> _subtree_size;
    std::vector<int> _heavy;
    std::vector<edge_type> _heavy_edge;
    std::vector<std::vector<edge_type>> _children;

    static edge_type reversed_edge(edge_type e) {
        std::swap(e.from, e.to);
        return e;
    }

    const Path& node_path_down(int node) const {
        assert(0 <= node && node < int(_nodes.size()));
        assert(_nodes[node].path_down.has_value());
        return *_nodes[node].path_down;
    }

    const Path& node_path_up(int node) const {
        assert(0 <= node && node < int(_nodes.size()));
        assert(_nodes[node].path_up.has_value());
        return *_nodes[node].path_up;
    }

    const Point& node_point(int node) const {
        assert(0 <= node && node < int(_nodes.size()));
        assert(_nodes[node].point.has_value());
        return *_nodes[node].point;
    }

    void set_parent(int child, int parent) {
        if (child != -1) _nodes[child].parent = parent;
    }

    void recompute(int node) {
        auto& x = _nodes[node];
        if (x.type == node_type::Compress) {
            x.path_down = _compress_down(node_path_down(x.left), node_path_down(x.right), x.edge);
            x.path_up = _compress_up(node_path_up(x.right), node_path_up(x.left), reversed_edge(x.edge));
        } else if (x.type == node_type::Rake) {
            x.point = _rake(node_point(x.left), node_point(x.right));
        } else if (x.type == node_type::AddEdge) {
            x.point = _add_edge_down(node_path_down(x.left), x.edge);
        } else {
            const Point& side = x.left == -1 ? _point_id : node_point(x.left);
            Path path = _add_vertex(side, _values[x.vertex], x.vertex);
            x.path_down = path;
            x.path_up = std::move(path);
        }
    }

    int new_node(Node node) {
        int id = int(_nodes.size());
        _nodes.push_back(std::move(node));
        set_parent(_nodes[id].left, id);
        set_parent(_nodes[id].right, id);
        recompute(id);
        return id;
    }

    int new_compress(int left, int right, edge_type edge) {
        Node node;
        node.type = node_type::Compress;
        node.left = left;
        node.right = right;
        node.edge = edge;
        node.size = _nodes[left].size + _nodes[right].size;
        node.height = std::max(_nodes[left].height, _nodes[right].height) + 1;
        int id = new_node(std::move(node));
        if (0 <= edge.id && edge.id < int(_edge_node.size())) _edge_node[edge.id] = id;
        return id;
    }

    int new_rake(int left, int right) {
        Node node;
        node.type = node_type::Rake;
        node.left = left;
        node.right = right;
        node.size = _nodes[left].size + _nodes[right].size;
        node.height = std::max(_nodes[left].height, _nodes[right].height) + 1;
        return new_node(std::move(node));
    }

    int new_add_edge(int child, edge_type edge) {
        Node node;
        node.type = node_type::AddEdge;
        node.left = child;
        node.edge = edge;
        node.size = _nodes[child].size;
        node.height = _nodes[child].height + 1;
        int id = new_node(std::move(node));
        if (0 <= edge.id && edge.id < int(_edge_node.size())) _edge_node[edge.id] = id;
        return id;
    }

    int new_add_vertex(int side, int vertex) {
        Node node;
        node.type = node_type::AddVertex;
        node.left = side;
        node.vertex = vertex;
        node.size = 1 + (side == -1 ? 0 : _nodes[side].size);
        node.height = 1 + (side == -1 ? 0 : _nodes[side].height);
        int id = new_node(std::move(node));
        _vertex_node[vertex] = id;
        return id;
    }

    int weighted_split(const std::vector<int>& nodes, int l, int r) const {
        int total = 0;
        for (int i = l; i < r; i++) total += _nodes[nodes[i]].size;
        int left_sum = 0;
        for (int i = l; i + 1 < r; i++) {
            left_sum += _nodes[nodes[i]].size;
            if (2 * left_sum >= total) return i + 1;
        }
        return r - 1;
    }

    int build_rake(const std::vector<int>& nodes, int l, int r) {
        if (l == r) return -1;
        if (l + 1 == r) return nodes[l];
        int m = weighted_split(nodes, l, r);
        return new_rake(build_rake(nodes, l, m), build_rake(nodes, m, r));
    }

    int build_compress(const std::vector<int>& nodes, const std::vector<edge_type>& edges, int l, int r) {
        if (l + 1 == r) return nodes[l];
        int m = weighted_split(nodes, l, r);
        return new_compress(build_compress(nodes, edges, l, m), build_compress(nodes, edges, m, r), edges[m - 1]);
    }

    int build_vertex(int v) {
        std::vector<int> side_nodes;
        for (const auto& e : _children[v]) {
            if (e.to == _heavy[v]) continue;
            int child_path = build_path(e.to);
            side_nodes.push_back(new_add_edge(child_path, e));
        }
        return new_add_vertex(build_rake(side_nodes, 0, int(side_nodes.size())), v);
    }

    int build_path(int start) {
        std::vector<int> path_nodes;
        std::vector<edge_type> path_edges;
        for (int v = start; v != -1; v = _heavy[v]) {
            path_nodes.push_back(build_vertex(v));
            if (_heavy[v] != -1) path_edges.push_back(_heavy_edge[v]);
        }
        return build_compress(path_nodes, path_edges, 0, int(path_nodes.size()));
    }

    void recompute_up(int node) {
        while (node != -1) {
            recompute(node);
            node = _nodes[node].parent;
        }
    }

   public:
    RerootingStaticTopTree(const m1une::graph::Graph<T>& g, const std::vector<Vertex>& values, Point point_id,
                           CompressDown compress_down, CompressUp compress_up, Rake rake,
                           AddEdgeDown add_edge_down, AddEdgeUp add_edge_up, AddVertex add_vertex, int root = 0)
        : _n(g.size()),
          _root(_n == 0 ? -1 : root),
          _root_node(-1),
          _point_id(std::move(point_id)),
          _compress_down(std::move(compress_down)),
          _compress_up(std::move(compress_up)),
          _rake(std::move(rake)),
          _add_edge_down(std::move(add_edge_down)),
          _add_edge_up(std::move(add_edge_up)),
          _add_vertex(std::move(add_vertex)),
          _values(values) {
        build(g, root);
    }

    void build(const m1une::graph::Graph<T>& g, int root = 0) {
        _n = g.size();
        _root = _n == 0 ? -1 : root;
        assert(int(_values.size()) == _n);
        _nodes.clear();
        _vertex_node.assign(_n, -1);
        _edge_node.assign(g.edge_count(), -1);
        _parent.assign(_n, -2);
        _subtree_size.assign(_n, 1);
        _heavy.assign(_n, -1);
        _heavy_edge.assign(_n, edge_type());
        _children.assign(_n, {});
        _root_node = -1;

        if (_n == 0) return;
        assert(0 <= root && root < _n);
        assert(int(g.edges().size()) == _n - 1);

        std::vector<int> order;
        order.reserve(_n);
        std::vector<int> stack = {root};
        _parent[root] = -1;
        while (!stack.empty()) {
            int v = stack.back();
            stack.pop_back();
            order.push_back(v);
            for (const auto& e : g[v]) {
                if (!e.alive) continue;
                if (_parent[e.to] != -2) continue;
                _parent[e.to] = v;
                _children[v].push_back(e);
                stack.push_back(e.to);
            }
        }
        assert(int(order.size()) == _n);

        for (int i = int(order.size()) - 1; i >= 0; i--) {
            int v = order[i];
            for (const auto& e : _children[v]) {
                _subtree_size[v] += _subtree_size[e.to];
                if (_heavy[v] == -1 || _subtree_size[_heavy[v]] < _subtree_size[e.to]) {
                    _heavy[v] = e.to;
                    _heavy_edge[v] = e;
                }
            }
        }

        _root_node = build_path(root);
    }

    int size() const {
        return _n;
    }

    bool empty() const {
        return _n == 0;
    }

    int root() const {
        return _root;
    }

    int root_node() const {
        return _root_node;
    }

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

    int height() const {
        return _root_node == -1 ? 0 : _nodes[_root_node].height;
    }

    const std::vector<Node>& nodes() const {
        return _nodes;
    }

    const Node& node(int id) const {
        assert(0 <= id && id < int(_nodes.size()));
        return _nodes[id];
    }

    int parent_node(int id) const {
        return node(id).parent;
    }

    int vertex_node(int v) const {
        assert(0 <= v && v < _n);
        return _vertex_node[v];
    }

    int local_point_node(int v) const {
        int id = vertex_node(v);
        assert(_nodes[id].type == node_type::AddVertex);
        return _nodes[id].left;
    }

    const Point& local_point(int v) const {
        int point_node = local_point_node(v);
        return point_node == -1 ? _point_id : node_point(point_node);
    }

    const Vertex& get(int v) const {
        assert(0 <= v && v < _n);
        return _values[v];
    }

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

    void set(int v, const Vertex& value) {
        assert(0 <= v && v < _n);
        assert(_vertex_node[v] != -1);
        _values[v] = value;
        recompute_up(_vertex_node[v]);
    }

    void set(int v, Vertex&& value) {
        assert(0 <= v && v < _n);
        assert(_vertex_node[v] != -1);
        _values[v] = std::move(value);
        recompute_up(_vertex_node[v]);
    }

    void set_edge_cost(int edge_id, T cost) {
        assert(0 <= edge_id && edge_id < int(_edge_node.size()));
        int node = _edge_node[edge_id];
        assert(node != -1);
        _nodes[node].edge.cost = cost;
        recompute_up(node);
    }

    const Path& path_down(int node_id) const {
        return node_path_down(node_id);
    }

    const Path& path_up(int node_id) const {
        return node_path_up(node_id);
    }

    const Point& point(int node_id) const {
        return node_point(node_id);
    }

    const Path& all_prod_down() const {
        assert(_root_node != -1);
        return path_down(_root_node);
    }

    const Path& all_prod_up() const {
        assert(_root_node != -1);
        return path_up(_root_node);
    }

    const Point& point_id() const {
        return _point_id;
    }

    template <class F>
    void for_each_rerooting_step(int v, F&& f) const {
        assert(0 <= v && v < _n);
        int cur = _vertex_node[v];
        assert(cur != -1);
        while (_nodes[cur].parent != -1) {
            int par = _nodes[cur].parent;
            const auto& p = _nodes[par];
            RerootingStep step;
            step.node = par;
            if (p.type == node_type::Compress) {
                step.edge = p.edge;
                if (p.left == cur) {
                    step.type = step_type::CompressLower;
                    step.sibling = p.right;
                } else {
                    assert(p.right == cur);
                    step.type = step_type::CompressUpper;
                    step.sibling = p.left;
                }
            } else if (p.type == node_type::Rake) {
                if (p.left == cur) {
                    step.type = step_type::RakeRight;
                    step.sibling = p.right;
                } else {
                    assert(p.right == cur);
                    step.type = step_type::RakeLeft;
                    step.sibling = p.left;
                }
            } else if (p.type == node_type::AddEdge) {
                assert(p.left == cur);
                step.type = step_type::AddEdge;
                step.edge = p.edge;
            } else {
                assert(p.type == node_type::AddVertex);
                assert(p.left == cur);
                step.type = step_type::AddVertex;
                step.vertex = p.vertex;
            }
            f(step);
            cur = par;
        }
    }

    std::vector<RerootingStep> rerooting_steps(int v) const {
        std::vector<RerootingStep> result;
        int cur = vertex_node(v);
        int depth = 0;
        while (_nodes[cur].parent != -1) {
            cur = _nodes[cur].parent;
            depth++;
        }
        result.reserve(depth);
        for_each_rerooting_step(v, [&](const RerootingStep& step) {
            result.push_back(step);
        });
        return result;
    }

    template <class Folder>
    auto fold_rerooting(int v, Folder folder) const {
        folder.start(v, _values[v], local_point(v));
        for_each_rerooting_step(v, [&](const RerootingStep& step) {
            if (step.type == step_type::CompressLower) {
                folder.compress_lower(path_down(step.sibling), step.edge);
            } else if (step.type == step_type::CompressUpper) {
                folder.compress_upper(path_up(step.sibling), reversed_edge(step.edge));
            } else if (step.type == step_type::AddEdge) {
                folder.add_edge(reversed_edge(step.edge));
            } else if (step.type == step_type::RakeLeft) {
                folder.rake_left(point(step.sibling));
            } else if (step.type == step_type::RakeRight) {
                folder.rake_right(point(step.sibling));
            } else {
                folder.add_vertex(step.vertex, _values[step.vertex]);
            }
        });
        return folder.result();
    }

    Path compress_down(const Path& upper, const Path& lower, edge_type edge) const {
        return _compress_down(upper, lower, edge);
    }

    Path compress_up(const Path& lower, const Path& upper, edge_type edge) const {
        return _compress_up(lower, upper, edge);
    }

    Point rake(const Point& left, const Point& right) const {
        return _rake(left, right);
    }

    Point add_edge_down(const Path& path, edge_type edge) const {
        return _add_edge_down(path, edge);
    }

    Point add_edge_up(const Path& path, edge_type edge) const {
        return _add_edge_up(path, edge);
    }

    Path add_vertex(const Point& side, const Vertex& value, int vertex) const {
        return _add_vertex(side, value, vertex);
    }

    static edge_type reverse_edge(edge_type edge) {
        return reversed_edge(edge);
    }
};

template <class T, class Vertex, class Point, class CompressDown, class CompressUp, class Rake, class AddEdgeDown,
          class AddEdgeUp, class AddVertex>
RerootingStaticTopTree(const m1une::graph::Graph<T>&, const std::vector<Vertex>&, Point, CompressDown, CompressUp,
                       Rake, AddEdgeDown, AddEdgeUp, AddVertex, int)
    -> RerootingStaticTopTree<T, Vertex, std::invoke_result_t<AddVertex, Point, Vertex, int>, Point, CompressDown,
                              CompressUp, Rake, AddEdgeDown, AddEdgeUp, AddVertex>;

template <class T, class Vertex, class Point, class CompressDown, class CompressUp, class Rake, class AddEdgeDown,
          class AddEdgeUp, class AddVertex>
RerootingStaticTopTree(const m1une::graph::Graph<T>&, const std::vector<Vertex>&, Point, CompressDown, CompressUp,
                       Rake, AddEdgeDown, AddEdgeUp, AddVertex)
    -> RerootingStaticTopTree<T, Vertex, std::invoke_result_t<AddVertex, Point, Vertex, int>, Point, CompressDown,
                              CompressUp, Rake, AddEdgeDown, AddEdgeUp, AddVertex>;

}  // namespace tree
}  // namespace m1une

m1une's library

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

Rerooting Static Top Tree
(graph/tree/rerooting_static_top_tree.hpp)

Overview

Cluster Types

Operations

What Is Stored

Rerooting Steps

Public Members

Using It In Problems

Example: ABC460 G - Vertex Flip Query

Example: Directional Distance Aggregates

Notes

Depends on

Required by

Verified with

Code

Rerooting Static Top Tree (graph/tree/rerooting_static_top_tree.hpp)

Overview

Cluster Types

Operations

What Is Stored

Rerooting Steps

Public Members

Using It In Problems

Example: ABC460 G - Vertex Flip Query

Example: Directional Distance Aggregates

Notes

Depends on

Required by

Verified with

Code

Rerooting Static Top Tree
(graph/tree/rerooting_static_top_tree.hpp)