オイラーツアー (lib/tree/euler_tour.hpp)

• View this file on GitHub
• Last update: 2025-06-10 13:56:45+09:00
• Include: #include "lib/tree/euler_tour.hpp"

Depends on

• 重み付きグラフ (lib/graph/graph.hpp)

Required by

• lib/tree/auxiliary_tree.hpp

Verified with

• test/aoj/challenge/2871.test.cpp
• test/yosupo/tree/vertex_add_subtree_sum.test.cpp
• test/yukicoder/0901.test.cpp

Code

#pragma once
#include <stack>
#include <utility>
#include <vector>
#include "graph/graph.hpp"

/// @brief オイラーツアー
struct euler_tour {
    template <class T>
    euler_tour(const Graph<T> &g, int r = 0) : euler_tour(g, g.size(), r) {}

    std::pair<int, int> operator[](int i) const { return std::make_pair(ls[i], rs[i]); }

    int size() const { return _size; }

    int left(int i) const { return ls[i]; }
    int right(int i) const { return rs[i]; }
    int order(int i) const { return ord[i]; }

    template <class F>
    void query(int v, const F &f) const {
        f(ls[v], rs[v]);
    }

  private:
    int _size;
    std::vector<int> ord, ls, rs;

    template <class T>
    euler_tour(const Graph<T> &g, int n, int r) : _size(n), ord(n), ls(n, -1), rs(n) {
        int c = 0;
        std::stack<int> st;
        st.emplace(r);
        while (!st.empty()) {
            auto x = st.top();
            st.pop();
            if (x < 0) {
                rs[~x] = c;
                continue;
            }
            ls[x] = c;
            ord[x] = c++;
            rs[x] = c;
            for (auto e : g[x]) {
                if (ls[e.to()] != -1) continue;
                st.emplace(~x);
                st.emplace(e.to());
            }
        }
    }
};

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/resolver.py", line 291, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 242, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 479, in update
    self._resolve(pathlib.Path(included), included_from=path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 286, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: graph/graph.hpp: line -1: no such header

Back to top page