add Euler tour

hitonanode · hitonanode · commit 58551908d281 · 2025-01-03T09:47:51.000+09:00
diff --git a/tree/euler_tour.hpp b/tree/euler_tour.hpp
@@ -0,0 +1,64 @@
+#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;
+    }
+};
diff --git a/tree/euler_tour.md b/tree/euler_tour.md
@@ -0,0 +1,38 @@
+---
+title: Euler tour （木のオイラーツアー）
+documentation_of: ./euler_tour.hpp
+---
+
+木のオイラーツアーを構築．パスクエリをデータ構造に載せて高速に解く場合や， Mo's algorithm を適用する場合に有用．
+
+## 使用方法
+
+以下で構築できる．
+
+```cpp
+int n, root;
+vector<pair<int, int>> edges;
+
+const euler_tour et(n, edges, root);
+```
+
+木上の $u$-$v$ パスに着目したい場合，以下の処理を行うと，当該パスを構成する辺が半開区間 `[begins, ends)` に丁度奇数回登場する．
+
+```cpp
+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](https://www.codechef.com/problems/DISTNUM3)
+  - 木のパス上の頂点集合に関するクエリを Mo's algorithm で解く．
+
+## 参考文献・リンク
+
+- [Mo's algorithm - ei1333の日記](https://ei1333.hateblo.jp/entry/2017/09/11/211011)
