:warning: LCA ベースの Auxiliary Tree
(tree/lca-auxiliary-tree.hpp)

Depends on

Code

#pragma once
#include "tree/lowest-common-ancestor.hpp"

struct LCAAuxiliaryTree : LowestCommonAncestor {
  using base = LowestCommonAncestor;
  LCAAuxiliaryTree(int size, int root = 0) : base(size, root) {}
  LCAAuxiliaryTree(vector<vector<int>>& graph, int root = 0) : base(graph, root) {}
  pair<int, vector<int>> calc(vector<int> vs, vector<vector<int>>& g) {
    if (vs.empty()) return {-1, vector<int>{}};
    int n = vs.size();
    sort(vs.begin(), vs.end(), [&](int x, int y) { return in_time[x] < in_time[y]; });
    stack<int> st;
    st.push(vs[0]);
    g[vs[0]] = {};
    for (int i = 0; i < n - 1; i++) {
      int x = vs[i], y = vs[i + 1];
      int w = lca(x, y);
      if (w != x) {
        int last = st.top();
        st.pop();
        while (!st.empty() && depth[w] < depth[st.top()]) {
          g[st.top()].push_back(last);
          last = st.top();
          st.pop();
        }
        if (st.empty() || st.top() != w) {
          st.push(w);
          vs.push_back(w);
          g[w] = {last};
        } else
          g[w].push_back(last);
      }
      st.push(y);
      g[y] = {};
    }
    int prv = st.top();
    st.pop();
    while (!st.empty()) {
      g[st.top()].push_back(prv);
      prv = st.top();
      st.pop();
    }
    sort(vs.begin(), vs.end(), [&](int x, int y) { return in_time[x] < in_time[y]; });
    return {prv, vs};
  }
};
/**
 * @brief LCA ベースの Auxiliary Tree
 * @docs docs/tree/lca-auxiliary-tree.md
 */
#line 2 "data-structure/sparse-table.hpp"

template <class T, T (*op)(T, T)>
struct SparseTable {
 private:
  int n;
  vector<vector<T>> st;

 public:
  SparseTable() {}
  SparseTable(const vector<T> &arr) {
    n = arr.size();
    int log = 1;
    while (n >> log) log++;
    st = vector<vector<T>>(log);
    st[0] = vector<T>(arr.begin(), arr.end());
    for (int k = 1; k < log; k++) {
      auto stp = st[k - 1];
      auto sti = vector<T>(n - (1 << k) + 1);
      for (int i = 0; i < sti.size(); i++)
        sti[i] = op(stp[i], stp[i + (1 << (k - 1))]);
      st[k] = sti;
    }
  }
  T prod(int l, int r)  // [l,r)
  {
    assert(0 <= l && l < r && r <= n);
    int j = 0;
    while ((2 << j) <= r - l) j++;
    return op(st[j][l], st[j][r - (1 << j)]);
  }
};
#line 3 "tree/lowest-common-ancestor.hpp"

struct LowestCommonAncestor {
  using P = pair<int, int>;
  static P lca_st_op(P x, P y) { return x.second <= y.second ? x : y; }

 protected:
  int n, r;
  vector<vector<int>> g;
  SparseTable<P, lca_st_op> st;
  vector<int> in_time, depth, parent, euler_tour;

 public:
  const int size() { return n; }
  const int root() { return r; }
  LowestCommonAncestor() {}
  LowestCommonAncestor(int size, int root = 0) : n(size), r(root), g(n) {}
  LowestCommonAncestor(const vector<vector<int>>& graph, int root = 0) : n(graph.size()), r(root), g(graph) {
    build();
  }
  void add_edge(int u, int v) {
    g[u].push_back(v);
    g[v].push_back(u);
  }
  void build() {
    parent.resize(n, -1);
    depth.resize(n, 0);
    in_time.resize(n, 0);
    euler_tour.reserve(2 * n - 1);
    {
      stack<int> st;
      st.push(r);
      vector<int> idx(n);
      while (!st.empty()) {
        int x = st.top();
        st.pop();
        if (idx[x] == 0) in_time[x] = euler_tour.size();
        euler_tour.push_back(x);
        if (idx[x] < g[x].size()) {
          st.push(x);
          int y = g[x][idx[x]++];
          if (y != parent[x]) {
            parent[y] = x;
            depth[y] = depth[x] + 1;
            st.push(y);
          }
        }
      }
    }
    vector<P> data;
    data.reserve(euler_tour.size());
    for (auto v : euler_tour)
      data.push_back({v, depth[v]});
    st = SparseTable<P, lca_st_op>(data);
  }
  int lca(int u, int v) {
    assert(0 <= u && u < n);
    assert(0 <= v && v < n);
    int x = in_time[u], y = in_time[v];
    if (x > y) swap(x, y);
    return st.prod(x, y + 1).first;
  }
};
/**
 * @brief Lowest Common Ancestor
 * @docs docs/tree/lowest-common-ancestor.md
 */
#line 3 "tree/lca-auxiliary-tree.hpp"

struct LCAAuxiliaryTree : LowestCommonAncestor {
  using base = LowestCommonAncestor;
  LCAAuxiliaryTree(int size, int root = 0) : base(size, root) {}
  LCAAuxiliaryTree(vector<vector<int>>& graph, int root = 0) : base(graph, root) {}
  pair<int, vector<int>> calc(vector<int> vs, vector<vector<int>>& g) {
    if (vs.empty()) return {-1, vector<int>{}};
    int n = vs.size();
    sort(vs.begin(), vs.end(), [&](int x, int y) { return in_time[x] < in_time[y]; });
    stack<int> st;
    st.push(vs[0]);
    g[vs[0]] = {};
    for (int i = 0; i < n - 1; i++) {
      int x = vs[i], y = vs[i + 1];
      int w = lca(x, y);
      if (w != x) {
        int last = st.top();
        st.pop();
        while (!st.empty() && depth[w] < depth[st.top()]) {
          g[st.top()].push_back(last);
          last = st.top();
          st.pop();
        }
        if (st.empty() || st.top() != w) {
          st.push(w);
          vs.push_back(w);
          g[w] = {last};
        } else
          g[w].push_back(last);
      }
      st.push(y);
      g[y] = {};
    }
    int prv = st.top();
    st.pop();
    while (!st.empty()) {
      g[st.top()].push_back(prv);
      prv = st.top();
      st.pop();
    }
    sort(vs.begin(), vs.end(), [&](int x, int y) { return in_time[x] < in_time[y]; });
    return {prv, vs};
  }
};
/**
 * @brief LCA ベースの Auxiliary Tree
 * @docs docs/tree/lca-auxiliary-tree.md
 */
Back to top page