Euler tour （木のオイラーツアー）
(tree/euler_tour.hpp)

• View this file on GitHub
• Last update: 2025-01-03 09:47:51+09:00
• Include: #include "tree/euler_tour.hpp"
• Link: https://maspypy.com/euler-tour-%E3%81%AE%E3%81%8A%E5%8B%89%E5%BC%B7

木のオイラーツアーを構築．パスクエリをデータ構造に載せて高速に解く場合や， Mo’s algorithm を適用する場合に有用．

使用方法

以下で構築できる．

int n, root;
vector<pair<int, int>> edges;

const euler_tour et(n, edges, root);

木上の $u$-$v$ パスに着目したい場合，以下の処理を行うと，当該パスを構成する辺が半開区間 [begins, ends) に丁度奇数回登場する．

int begins = et.begins.at(u), ends = et.begins.at(v);

for (int i = begins; i < ends; ++i) {
    // Insert or erase et.tour_child(i);
}

半開区間 [begins, ends) たちに対して Mo’s algorithm などを適用することで，クエリたちが効率的に処理できることがある．

問題例

• Primitive Queries | CodeChef
  • 木のパス上の頂点集合に関するクエリを Mo’s algorithm で解く．

参考文献・リンク

• Mo’s algorithm - ei1333の日記

Code

#pragma once
#include <cassert>
#include <utility>
#include <vector>

// Euler tour
// https://maspypy.com/euler-tour-%E3%81%AE%E3%81%8A%E5%8B%89%E5%BC%B7
struct euler_tour {
    int n;
    int root;

    std::vector<std::pair<int, int>> edges; // (parent, child)

    // - 頂点 v に関する部分木に含まれる辺は， [begins[v], ends[v]) に 2 回ずつ登場
    // - [begins[u], begins[v]) (begins[u] <= begins[v]) の半開区間に u-v パスを構成する辺が奇数回登場
    std::vector<int> begins;
    std::vector<int> ends;

    std::vector<int> par_eid;
    std::vector<std::pair<int, bool>> tour; // (edge_id, flg) flg=true: down, false: up

    void _build_dfs(int now, int prv_eid, const std::vector<std::vector<std::pair<int, int>>> &to) {
        tour.emplace_back(prv_eid, true);
        begins[now] = tour.size();

        for (auto [nxt, eid] : to[now]) {
            if (eid == prv_eid) continue;
            par_eid[nxt] = eid;
            if (edges[eid].first == nxt) std::swap(edges[eid].first, edges[eid].second);
            _build_dfs(nxt, eid, to);
        }

        ends[now] = tour.size();
        tour.emplace_back(prv_eid, false);
    }

    euler_tour() = default;

    euler_tour(int n, const std::vector<std::pair<int, int>> &edges_, int root)
        : n(n), root(root), edges(edges_), begins(n, -1), ends(n, -1), par_eid(n, -1) {
        std::vector<std::vector<std::pair<int, int>>> to(n);
        for (int eid = 0; eid < (int)edges.size(); ++eid) {
            auto [u, v] = edges[eid];
            assert(u != v);
            to.at(u).emplace_back(v, eid);
            to.at(v).emplace_back(u, eid);
        }

        _build_dfs(root, -1, to);
    }

    // 頂点 v の部分木の頂点数
    int subtree_size(int v) const { return (ends.at(v) - begins.at(v)) / 2 + 1; }

    int par(int v) const {
        int eid = par_eid.at(v);
        return eid == -1 ? -1 : edges[eid].first;
    }

    int tour_child(int idx) const {
        int eid = tour.at(idx).first;
        return eid < 0 ? root : edges[eid].second;
    }
};

#line 2 "tree/euler_tour.hpp"
#include <cassert>
#include <utility>
#include <vector>

// Euler tour
// https://maspypy.com/euler-tour-%E3%81%AE%E3%81%8A%E5%8B%89%E5%BC%B7
struct euler_tour {
    int n;
    int root;

    std::vector<std::pair<int, int>> edges; // (parent, child)

    // - 頂点 v に関する部分木に含まれる辺は， [begins[v], ends[v]) に 2 回ずつ登場
    // - [begins[u], begins[v]) (begins[u] <= begins[v]) の半開区間に u-v パスを構成する辺が奇数回登場
    std::vector<int> begins;
    std::vector<int> ends;

    std::vector<int> par_eid;
    std::vector<std::pair<int, bool>> tour; // (edge_id, flg) flg=true: down, false: up

    void _build_dfs(int now, int prv_eid, const std::vector<std::vector<std::pair<int, int>>> &to) {
        tour.emplace_back(prv_eid, true);
        begins[now] = tour.size();

        for (auto [nxt, eid] : to[now]) {
            if (eid == prv_eid) continue;
            par_eid[nxt] = eid;
            if (edges[eid].first == nxt) std::swap(edges[eid].first, edges[eid].second);
            _build_dfs(nxt, eid, to);
        }

        ends[now] = tour.size();
        tour.emplace_back(prv_eid, false);
    }

    euler_tour() = default;

    euler_tour(int n, const std::vector<std::pair<int, int>> &edges_, int root)
        : n(n), root(root), edges(edges_), begins(n, -1), ends(n, -1), par_eid(n, -1) {
        std::vector<std::vector<std::pair<int, int>>> to(n);
        for (int eid = 0; eid < (int)edges.size(); ++eid) {
            auto [u, v] = edges[eid];
            assert(u != v);
            to.at(u).emplace_back(v, eid);
            to.at(v).emplace_back(u, eid);
        }

        _build_dfs(root, -1, to);
    }

    // 頂点 v の部分木の頂点数
    int subtree_size(int v) const { return (ends.at(v) - begins.at(v)) / 2 + 1; }

    int par(int v) const {
        int eid = par_eid.at(v);
        return eid == -1 ? -1 : edges[eid].first;
    }

    int tour_child(int idx) const {
        int eid = tour.at(idx).first;
        return eid < 0 ? root : edges[eid].second;
    }
};

Back to top page