Rooted Tree
(graph/tree/rooted_tree.hpp)

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

Overview

m1une::tree::RootedTree<T> preprocesses an undirected tree for rooted-tree queries. It uses the existing m1une::graph::Graph<T> container, so build the input with add_edge.

The structure stores parent/depth/subtree metadata, Euler-tour intervals, binary lifting tables, LCA queries, path restoration, and weighted distances.

Inactive graph edges are ignored.

Construction

m1une::graph::Graph<long long> g(n);
g.add_edge(u, v, w);

m1une::tree::RootedTree<long long> tree(g, 0);

The graph is expected to be an undirected tree. If the graph is disconnected, only the component reachable from the selected root is represented.

Public Members

Member	Type	Description
root	int	Root vertex, or -1 for an empty tree.
parent	std::vector<int>	Parent vertex, or -1 at the root.
parent_edge	std::vector<int>	Edge id connecting the vertex to its parent, or -1.
depth	std::vector<int>	Number of edges from the root.
dist	std::vector<T>	Sum of edge costs from the root.
subtree_size	std::vector<int>	Number of vertices in each rooted subtree.
tin, tout	std::vector<int>	Euler-tour interval [tin[v], tout[v]) for each subtree.
order	std::vector<int>	Vertices in DFS preorder.
up	std::vector<std::vector<int>>	Binary lifting table.

Methods

Method	Description	Complexity
RootedTree(g, root)	Builds rooted-tree data.	$O(N \log N)$
void build(g, root)	Rebuilds the structure.	$O(N \log N)$
int size()	Returns the number of vertices in the source graph.	$O(1)$
bool empty()	Returns whether the source graph is empty.	$O(1)$
int log()	Returns the number of binary-lifting levels.	$O(1)$
bool is_ancestor(u, v)	Returns whether u is an ancestor of v.	$O(1)$
bool in_subtree(v, u)	Returns whether v is in the subtree of u.	$O(1)$
int kth_ancestor(v, k)	Returns the k-th ancestor of v, or -1.	$O(\log N)$
int lca(u, v)	Returns the lowest common ancestor.	$O(\log N)$
int dist_edges(u, v)	Returns the number of edges on the path.	$O(\log N)$
T dist_cost(u, v)	Returns the sum of edge costs on the path.	$O(\log N)$
int jump(from, to, k)	Returns the k-th vertex on the path from from to to, or -1.	$O(\log N)$
std::vector<int> path(u, v)	Restores the vertices on the path from u to v.	$O(\text{path length})$
std::vector<int> path_edges(u, v)	Restores edge ids on the path from u to v.	$O(\text{path length})$
std::pair<int, int> subtree_range(v)	Returns [tin[v], tout[v]).	$O(1)$
std::vector<int> subtree_vertices(v)	Returns vertices in the rooted subtree of v.	$O(\text{subtree size})$

Example

#include "graph/graph.hpp"
#include "graph/tree/rooted_tree.hpp"
#include <iostream>

int main() {
    m1une::graph::Graph<long long> g(4);
    g.add_edge(0, 1, 2);
    g.add_edge(1, 2, 3);
    g.add_edge(1, 3, 4);

    m1une::tree::RootedTree<long long> tree(g, 0);
    std::cout << tree.lca(2, 3) << "\n";       // 1
    std::cout << tree.dist_cost(2, 3) << "\n"; // 7
}

Depends on

• Graph (graph/graph.hpp)

Required by

• Graph All (graph/all.hpp)
• Tree All (graph/tree/all.hpp)
• Range Contour Query on Tree (graph/tree/range_contour_query.hpp)
• Tree (graph/tree/tree.hpp)
• 01 on Tree (graph/tree/zero_one_on_tree.hpp)

Verified with

• verify/graph/cow_game.test.cpp
• verify/graph/graph_algorithms.test.cpp
• verify/graph/range_edge_graph.test.cpp
• verify/graph/tree/tree_algorithms.test.cpp
• verify/graph/tree/tree_cumulative_sum.test.cpp
• verify/graph/tree/vertex_add_range_contour_sum_on_tree.test.cpp
• verify/graph/tree/vertex_get_range_contour_add_on_tree.test.cpp
• verify/graph/tree/zero_one_on_tree.test.cpp

Code

#ifndef M1UNE_TREE_ROOTED_TREE_HPP
#define M1UNE_TREE_ROOTED_TREE_HPP 1

#include <algorithm>
#include <cassert>
#include <vector>

#include "../graph.hpp"

namespace m1une {
namespace tree {

template <class T = int>
struct RootedTree {
    using cost_type = T;
    using edge_type = m1une::graph::Edge<T>;

    int root;
    std::vector<int> parent;
    std::vector<int> parent_edge;
    std::vector<int> depth;
    std::vector<T> dist;
    std::vector<int> subtree_size;
    std::vector<int> tin;
    std::vector<int> tout;
    std::vector<int> order;
    std::vector<std::vector<int>> up;

   private:
    int _n;
    int _log;

    void check_vertex(int v) const {
        assert(0 <= v && v < _n);
        assert(tin[v] != -1);
    }

   public:
    RootedTree() : root(-1), _n(0), _log(0) {}
    explicit RootedTree(const m1une::graph::Graph<T>& g, int root_ = 0) {
        build(g, root_);
    }

    void build(const m1une::graph::Graph<T>& g, int root_ = 0) {
        _n = g.size();
        root = _n == 0 ? -1 : root_;
        _log = 1;
        while ((1U << _log) <= (unsigned int)(std::max(1, _n))) _log++;

        parent.assign(_n, -1);
        parent_edge.assign(_n, -1);
        depth.assign(_n, 0);
        dist.assign(_n, T(0));
        subtree_size.assign(_n, 0);
        tin.assign(_n, -1);
        tout.assign(_n, -1);
        order.clear();
        order.reserve(_n);
        up.assign(_log, std::vector<int>(_n, -1));

        if (_n == 0) return;
        assert(0 <= root && root < _n);

        struct Frame {
            int v;
            int state;
        };

        std::vector<char> visited(_n, false);
        std::vector<Frame> stack;
        stack.push_back({root, 0});
        visited[root] = true;
        int timer = 0;

        while (!stack.empty()) {
            Frame frame = stack.back();
            stack.pop_back();
            int v = frame.v;
            if (frame.state == 0) {
                tin[v] = timer++;
                order.push_back(v);
                up[0][v] = parent[v];
                for (int k = 1; k < _log; k++) {
                    int p = up[k - 1][v];
                    up[k][v] = p == -1 ? -1 : up[k - 1][p];
                }

                stack.push_back({v, 1});
                const auto& adj = g[v];
                for (int i = int(adj.size()) - 1; i >= 0; i--) {
                    const auto& e = adj[i];
                    if (!e.alive) continue;
                    if (visited[e.to]) continue;
                    visited[e.to] = true;
                    parent[e.to] = v;
                    parent_edge[e.to] = e.id;
                    depth[e.to] = depth[v] + 1;
                    dist[e.to] = dist[v] + e.cost;
                    stack.push_back({e.to, 0});
                }
            } else {
                subtree_size[v]++;
                if (parent[v] != -1) subtree_size[parent[v]] += subtree_size[v];
                tout[v] = timer;
            }
        }
    }

    int size() const {
        return _n;
    }

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

    int log() const {
        return _log;
    }

    bool is_ancestor(int u, int v) const {
        check_vertex(u);
        check_vertex(v);
        return tin[u] <= tin[v] && tout[v] <= tout[u];
    }

    bool in_subtree(int v, int u) const {
        return is_ancestor(u, v);
    }

    int kth_ancestor(int v, int k) const {
        check_vertex(v);
        assert(0 <= k);
        int bit = 0;
        while (k > 0 && v != -1) {
            if (k & 1) {
                if (_log <= bit) return -1;
                v = up[bit][v];
            }
            k >>= 1;
            bit++;
        }
        return v;
    }

    int lca(int u, int v) const {
        check_vertex(u);
        check_vertex(v);
        if (depth[u] < depth[v]) std::swap(u, v);
        u = kth_ancestor(u, depth[u] - depth[v]);
        if (u == v) return u;
        for (int k = _log - 1; k >= 0; k--) {
            if (up[k][u] != up[k][v]) {
                u = up[k][u];
                v = up[k][v];
            }
        }
        return parent[u];
    }

    int dist_edges(int u, int v) const {
        int w = lca(u, v);
        return depth[u] + depth[v] - 2 * depth[w];
    }

    T dist_cost(int u, int v) const {
        int w = lca(u, v);
        return dist[u] + dist[v] - dist[w] - dist[w];
    }

    int jump(int from, int to, int k) const {
        check_vertex(from);
        check_vertex(to);
        assert(0 <= k);
        int w = lca(from, to);
        int up_len = depth[from] - depth[w];
        int down_len = depth[to] - depth[w];
        if (up_len + down_len < k) return -1;
        if (k <= up_len) return kth_ancestor(from, k);
        return kth_ancestor(to, down_len - (k - up_len));
    }

    std::vector<int> path(int u, int v) const {
        check_vertex(u);
        check_vertex(v);
        int w = lca(u, v);
        std::vector<int> a, b;
        for (int x = u; x != w; x = parent[x]) a.push_back(x);
        a.push_back(w);
        for (int x = v; x != w; x = parent[x]) b.push_back(x);
        std::reverse(b.begin(), b.end());
        a.insert(a.end(), b.begin(), b.end());
        return a;
    }

    std::vector<int> path_edges(int u, int v) const {
        check_vertex(u);
        check_vertex(v);
        int w = lca(u, v);
        std::vector<int> a, b;
        for (int x = u; x != w; x = parent[x]) a.push_back(parent_edge[x]);
        for (int x = v; x != w; x = parent[x]) b.push_back(parent_edge[x]);
        std::reverse(b.begin(), b.end());
        a.insert(a.end(), b.begin(), b.end());
        return a;
    }

    std::pair<int, int> subtree_range(int v) const {
        check_vertex(v);
        return {tin[v], tout[v]};
    }

    std::vector<int> subtree_vertices(int v) const {
        check_vertex(v);
        return std::vector<int>(order.begin() + tin[v], order.begin() + tout[v]);
    }
};

}  // namespace tree
}  // namespace m1une

#endif  // M1UNE_TREE_ROOTED_TREE_HPP

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



#include <algorithm>
#include <cassert>
#include <vector>

#line 1 "graph/graph.hpp"



#include <array>
#line 6 "graph/graph.hpp"
#include <utility>
#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 9 "graph/tree/rooted_tree.hpp"

namespace m1une {
namespace tree {

template <class T = int>
struct RootedTree {
    using cost_type = T;
    using edge_type = m1une::graph::Edge<T>;

    int root;
    std::vector<int> parent;
    std::vector<int> parent_edge;
    std::vector<int> depth;
    std::vector<T> dist;
    std::vector<int> subtree_size;
    std::vector<int> tin;
    std::vector<int> tout;
    std::vector<int> order;
    std::vector<std::vector<int>> up;

   private:
    int _n;
    int _log;

    void check_vertex(int v) const {
        assert(0 <= v && v < _n);
        assert(tin[v] != -1);
    }

   public:
    RootedTree() : root(-1), _n(0), _log(0) {}
    explicit RootedTree(const m1une::graph::Graph<T>& g, int root_ = 0) {
        build(g, root_);
    }

    void build(const m1une::graph::Graph<T>& g, int root_ = 0) {
        _n = g.size();
        root = _n == 0 ? -1 : root_;
        _log = 1;
        while ((1U << _log) <= (unsigned int)(std::max(1, _n))) _log++;

        parent.assign(_n, -1);
        parent_edge.assign(_n, -1);
        depth.assign(_n, 0);
        dist.assign(_n, T(0));
        subtree_size.assign(_n, 0);
        tin.assign(_n, -1);
        tout.assign(_n, -1);
        order.clear();
        order.reserve(_n);
        up.assign(_log, std::vector<int>(_n, -1));

        if (_n == 0) return;
        assert(0 <= root && root < _n);

        struct Frame {
            int v;
            int state;
        };

        std::vector<char> visited(_n, false);
        std::vector<Frame> stack;
        stack.push_back({root, 0});
        visited[root] = true;
        int timer = 0;

        while (!stack.empty()) {
            Frame frame = stack.back();
            stack.pop_back();
            int v = frame.v;
            if (frame.state == 0) {
                tin[v] = timer++;
                order.push_back(v);
                up[0][v] = parent[v];
                for (int k = 1; k < _log; k++) {
                    int p = up[k - 1][v];
                    up[k][v] = p == -1 ? -1 : up[k - 1][p];
                }

                stack.push_back({v, 1});
                const auto& adj = g[v];
                for (int i = int(adj.size()) - 1; i >= 0; i--) {
                    const auto& e = adj[i];
                    if (!e.alive) continue;
                    if (visited[e.to]) continue;
                    visited[e.to] = true;
                    parent[e.to] = v;
                    parent_edge[e.to] = e.id;
                    depth[e.to] = depth[v] + 1;
                    dist[e.to] = dist[v] + e.cost;
                    stack.push_back({e.to, 0});
                }
            } else {
                subtree_size[v]++;
                if (parent[v] != -1) subtree_size[parent[v]] += subtree_size[v];
                tout[v] = timer;
            }
        }
    }

    int size() const {
        return _n;
    }

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

    int log() const {
        return _log;
    }

    bool is_ancestor(int u, int v) const {
        check_vertex(u);
        check_vertex(v);
        return tin[u] <= tin[v] && tout[v] <= tout[u];
    }

    bool in_subtree(int v, int u) const {
        return is_ancestor(u, v);
    }

    int kth_ancestor(int v, int k) const {
        check_vertex(v);
        assert(0 <= k);
        int bit = 0;
        while (k > 0 && v != -1) {
            if (k & 1) {
                if (_log <= bit) return -1;
                v = up[bit][v];
            }
            k >>= 1;
            bit++;
        }
        return v;
    }

    int lca(int u, int v) const {
        check_vertex(u);
        check_vertex(v);
        if (depth[u] < depth[v]) std::swap(u, v);
        u = kth_ancestor(u, depth[u] - depth[v]);
        if (u == v) return u;
        for (int k = _log - 1; k >= 0; k--) {
            if (up[k][u] != up[k][v]) {
                u = up[k][u];
                v = up[k][v];
            }
        }
        return parent[u];
    }

    int dist_edges(int u, int v) const {
        int w = lca(u, v);
        return depth[u] + depth[v] - 2 * depth[w];
    }

    T dist_cost(int u, int v) const {
        int w = lca(u, v);
        return dist[u] + dist[v] - dist[w] - dist[w];
    }

    int jump(int from, int to, int k) const {
        check_vertex(from);
        check_vertex(to);
        assert(0 <= k);
        int w = lca(from, to);
        int up_len = depth[from] - depth[w];
        int down_len = depth[to] - depth[w];
        if (up_len + down_len < k) return -1;
        if (k <= up_len) return kth_ancestor(from, k);
        return kth_ancestor(to, down_len - (k - up_len));
    }

    std::vector<int> path(int u, int v) const {
        check_vertex(u);
        check_vertex(v);
        int w = lca(u, v);
        std::vector<int> a, b;
        for (int x = u; x != w; x = parent[x]) a.push_back(x);
        a.push_back(w);
        for (int x = v; x != w; x = parent[x]) b.push_back(x);
        std::reverse(b.begin(), b.end());
        a.insert(a.end(), b.begin(), b.end());
        return a;
    }

    std::vector<int> path_edges(int u, int v) const {
        check_vertex(u);
        check_vertex(v);
        int w = lca(u, v);
        std::vector<int> a, b;
        for (int x = u; x != w; x = parent[x]) a.push_back(parent_edge[x]);
        for (int x = v; x != w; x = parent[x]) b.push_back(parent_edge[x]);
        std::reverse(b.begin(), b.end());
        a.insert(a.end(), b.begin(), b.end());
        return a;
    }

    std::pair<int, int> subtree_range(int v) const {
        check_vertex(v);
        return {tin[v], tout[v]};
    }

    std::vector<int> subtree_vertices(int v) const {
        check_vertex(v);
        return std::vector<int>(order.begin() + tin[v], order.begin() + tout[v]);
    }
};

}  // namespace tree
}  // namespace m1une

Back to top page