オイラーツアー
(tree/euler-tour.hpp)

• View this file on GitHub
• Last update: 2021-11-23 10:22:25+09:00
• Include: #include "tree/euler-tour.hpp"

Euler Tour

無向森が与えられたときにそれぞれの木に対してEuler Tourを構築するライブラリ。

概要

TODO: アルゴリズムの説明を書く

TODO: 森が与えられた時と辺クエリのverifyを書いていないので、書く

備忘録

• アーベル環を載せたパスクエリは$[\mathrm{down}(i)+1,\mathrm{down}(j)+1)$に$\mathrm{lca}(i,j)$を加えたもの！

• LCAを求めるときとパスクエリで記録する値が違う
  • LCAの時は原義のオイラーツアー(たぶん)
  • パスクエリは入る時と出る時を記録
• 逆元つきモノイドはEuler Tourでクエリ$\mathrm{O}(\log N)$
• 逆元なしモノイドはHL Decでクエリ$\mathrm{O}(\log^2 N)$

使い方

• EulerTour(g, root): グラフgに対してrootを最初の根とするオイラーツアーを構築する。
• lca(u, v):$\mathrm{lca}(u,v)$を返す。
• idx(i) : make_pair(down[i], up[i])を返す。ここでdown[i]は頂点iに入った時のid、up[i]は頂点iから出た時のidである。
• path_query(u, v, f): 頂点クエリ用の関数。
• edge_query(u, v, f): 辺クエリ用の関数。
• subtree_query(u, v, f): 部分木クエリ用の関数。

Depends on

• グラフテンプレート (graph/graph-template.hpp)

Verified with

• verify/verify-yosupo-ds/yosupo-vertex-add-path-sum-euler-tour.test.cpp
• verify/verify-yosupo-ds/yosupo-vertex-add-subtree-sum-euler-tree.test.cpp
• verify/verify-yosupo-graph/yosupo-lowest-common-ancestor-euler-tour.test.cpp

Code

#pragma once



#include "../graph/graph-template.hpp"

template <typename G>
struct EulerTour {
 private:
  struct RMQ {
    int n, s;
    using P = pair<int, int>;
    vector<P> seg;
    P UNIT = P(1 << 30, -1);

    RMQ(int N) : n(N), s(1) {
      while (s < N) s <<= 1;
      seg.assign(2 * s, UNIT);
    }

    void set(int k, P x) { seg[k + s] = x; }

    P operator[](int k) const { return seg[k + s]; }

    void build() {
      for (int k = s - 1; k > 0; k--) {
        seg[k] = min(seg[2 * k], seg[2 * k + 1]);
      }
    }

    P query(int a, int b) const {
      P R = UNIT;
      for (a += s, b += s; a < b; a >>= 1, b >>= 1) {
        if (a & 1) R = min(R, seg[a++]);
        if (b & 1) R = min(R, seg[--b]);
      }
      return R;
    }

    int size() const { return n; }
  };

  vector<int> down, up;
  int id;
  RMQ rmq;

  void init(G &g, int root) {
    dfs(g, root, -1, 0);
    if (id < rmq.size()) rmq.set(id++, {-1, -1});
    for (int i = 0; i < (int)g.size(); i++) {
      if (down[i] == -1) {
        rmq.set(id++, {-1, -1});
        dfs(g, i, -1, 0);
        if (id < rmq.size()) rmq.set(id++, {-1, -1});
      }
    }
    rmq.build();
  }

  void dfs(G &g, int c, int p, int dp) {
    down[c] = id;
    rmq.set(id++, {dp, c});
    for (auto &d : g[c]) {
      if (d == p) continue;
      dfs(g, d, c, dp + 1);
    }
    up[c] = id;
    if (p != -1) rmq.set(id++, {dp - 1, p});
  }

 public:
  // remind : because of additional node,
  // DS on tour should reserve 2 * n nodes.
  EulerTour(G &g, int root = 0)
      : down(g.size(), -1), up(g.size(), -1), id(0), rmq(2 * g.size()) {
    init(g, root);
  }

  pair<int, int> idx(int i) const { return {down[i], up[i]}; }

  int lca(int a, int b) const {
    if (down[a] > down[b]) swap(a, b);
    return rmq.query(down[a], down[b] + 1).second;
  }

  template <typename F>
  void node_query(int a, int b, const F &f) {
    int l = lca(a, b);
    f(down[l], down[a] + 1);
    f(down[l] + 1, down[b] + 1);
  }

  template <typename F>
  void edge_query(int a, int b, const F &f) {
    int l = lca(a, b);
    f(down[l] + 1, down[a] + 1);
    f(down[l] + 1, down[b] + 1);
  }

  template <typename F>
  void subtree_query(int a, const F &f) {
    f(down[a], up[a]);
  }

  int size() const { return int(rmq.size()); }
};

/**
 * @brief オイラーツアー
 * @docs docs/tree/euler-tour.md
 */

#line 2 "tree/euler-tour.hpp"



#line 2 "graph/graph-template.hpp"

template <typename T>
struct edge {
  int src, to;
  T cost;

  edge(int _to, T _cost) : src(-1), to(_to), cost(_cost) {}
  edge(int _src, int _to, T _cost) : src(_src), to(_to), cost(_cost) {}

  edge &operator=(const int &x) {
    to = x;
    return *this;
  }

  operator int() const { return to; }
};
template <typename T>
using Edges = vector<edge<T>>;
template <typename T>
using WeightedGraph = vector<Edges<T>>;
using UnweightedGraph = vector<vector<int>>;

// Input of (Unweighted) Graph
UnweightedGraph graph(int N, int M = -1, bool is_directed = false,
                      bool is_1origin = true) {
  UnweightedGraph g(N);
  if (M == -1) M = N - 1;
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    if (is_1origin) x--, y--;
    g[x].push_back(y);
    if (!is_directed) g[y].push_back(x);
  }
  return g;
}

// Input of Weighted Graph
template <typename T>
WeightedGraph<T> wgraph(int N, int M = -1, bool is_directed = false,
                        bool is_1origin = true) {
  WeightedGraph<T> g(N);
  if (M == -1) M = N - 1;
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    T c;
    cin >> c;
    if (is_1origin) x--, y--;
    g[x].emplace_back(x, y, c);
    if (!is_directed) g[y].emplace_back(y, x, c);
  }
  return g;
}

// Input of Edges
template <typename T>
Edges<T> esgraph(int N, int M, int is_weighted = true, bool is_1origin = true) {
  Edges<T> es;
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    T c;
    if (is_weighted)
      cin >> c;
    else
      c = 1;
    if (is_1origin) x--, y--;
    es.emplace_back(x, y, c);
  }
  return es;
}

// Input of Adjacency Matrix
template <typename T>
vector<vector<T>> adjgraph(int N, int M, T INF, int is_weighted = true,
                           bool is_directed = false, bool is_1origin = true) {
  vector<vector<T>> d(N, vector<T>(N, INF));
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    T c;
    if (is_weighted)
      cin >> c;
    else
      c = 1;
    if (is_1origin) x--, y--;
    d[x][y] = c;
    if (!is_directed) d[y][x] = c;
  }
  return d;
}

/**
 * @brief グラフテンプレート
 * @docs docs/graph/graph-template.md
 */
#line 6 "tree/euler-tour.hpp"

template <typename G>
struct EulerTour {
 private:
  struct RMQ {
    int n, s;
    using P = pair<int, int>;
    vector<P> seg;
    P UNIT = P(1 << 30, -1);

    RMQ(int N) : n(N), s(1) {
      while (s < N) s <<= 1;
      seg.assign(2 * s, UNIT);
    }

    void set(int k, P x) { seg[k + s] = x; }

    P operator[](int k) const { return seg[k + s]; }

    void build() {
      for (int k = s - 1; k > 0; k--) {
        seg[k] = min(seg[2 * k], seg[2 * k + 1]);
      }
    }

    P query(int a, int b) const {
      P R = UNIT;
      for (a += s, b += s; a < b; a >>= 1, b >>= 1) {
        if (a & 1) R = min(R, seg[a++]);
        if (b & 1) R = min(R, seg[--b]);
      }
      return R;
    }

    int size() const { return n; }
  };

  vector<int> down, up;
  int id;
  RMQ rmq;

  void init(G &g, int root) {
    dfs(g, root, -1, 0);
    if (id < rmq.size()) rmq.set(id++, {-1, -1});
    for (int i = 0; i < (int)g.size(); i++) {
      if (down[i] == -1) {
        rmq.set(id++, {-1, -1});
        dfs(g, i, -1, 0);
        if (id < rmq.size()) rmq.set(id++, {-1, -1});
      }
    }
    rmq.build();
  }

  void dfs(G &g, int c, int p, int dp) {
    down[c] = id;
    rmq.set(id++, {dp, c});
    for (auto &d : g[c]) {
      if (d == p) continue;
      dfs(g, d, c, dp + 1);
    }
    up[c] = id;
    if (p != -1) rmq.set(id++, {dp - 1, p});
  }

 public:
  // remind : because of additional node,
  // DS on tour should reserve 2 * n nodes.
  EulerTour(G &g, int root = 0)
      : down(g.size(), -1), up(g.size(), -1), id(0), rmq(2 * g.size()) {
    init(g, root);
  }

  pair<int, int> idx(int i) const { return {down[i], up[i]}; }

  int lca(int a, int b) const {
    if (down[a] > down[b]) swap(a, b);
    return rmq.query(down[a], down[b] + 1).second;
  }

  template <typename F>
  void node_query(int a, int b, const F &f) {
    int l = lca(a, b);
    f(down[l], down[a] + 1);
    f(down[l] + 1, down[b] + 1);
  }

  template <typename F>
  void edge_query(int a, int b, const F &f) {
    int l = lca(a, b);
    f(down[l] + 1, down[a] + 1);
    f(down[l] + 1, down[b] + 1);
  }

  template <typename F>
  void subtree_query(int a, const F &f) {
    f(down[a], up[a]);
  }

  int size() const { return int(rmq.size()); }
};

/**
 * @brief オイラーツアー
 * @docs docs/tree/euler-tour.md
 */

Back to top page