競プロ日記

問題
ACコード

#include <bits/stdc++.h>
#define GET_REP(_1, _2, _3, NAME, ...) NAME
#define rep(...) GET_REP(__VA_ARGS__, irep, _rep)(__VA_ARGS__)
#define rep1(...) GET_REP(__VA_ARGS__, irep1, _rep1)(__VA_ARGS__)
#define _rep(i, n) irep (i, 0, n)
#define _rep1(i, n) irep1(i, 1, n)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define irep1(i, a, n) for (int i = a; i <= (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(X, x) for (auto &&X : x)
#define all(x) (x).begin(), (x).end()
#ifdef LOCAL
  #include "../../Lib/cout_container.hpp"
  #define debug(x) cerr << #x " => " << x << endl
#else
  #define debug(x) 0
#endif
using lint = long long;
constexpr int    INF  = 1 << 30;
constexpr lint   INFL = 1LL << 62;
constexpr int    MOD  = (int)1e9 + 7;
constexpr double EPS  = 1e-9;
using namespace std;
namespace { struct INIT { INIT() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } INIT; }

using Weight = int;
struct Edge {
  int src, dst;
  Weight weight;
  Edge(void) {}
  Edge(int src, int dst) : src(src), dst(dst) {}
  Edge(int src, int dst, Weight weight) : src(src), dst(dst), weight(weight) {}
};
using Edges = vector;
using Graph = vector;

void edges_to_graph(Graph &graph, const Edges &edges, const int vertices, const bool directed = true) {
  graph.resize(vertices);
  for (const auto &e : edges) {
    graph[e.src].push_back(e);
    if (!directed) graph[e.dst].emplace_back(Edge(e.dst, e.src, e.weight));
  }
}

template 
class SparseTable {
  vector<vector> st;
  vector lookup;
  vector   vec;

  public:
  SparseTable(void) {}
  SparseTable(const vector &original_vecter) { init(original_vecter); }
  void init(const vector &original_vecter) {
    vec = original_vecter;
    int lgsize = 0, vsize = vec.size();
    while ((1 << lgsize) <= vsize) ++lgsize;
    st.assign((1 << lgsize), vector(lgsize));
    for (int i = 0; i < vsize; ++i) st[i][0] = i;
    for (int j = 1; j < lgsize; ++j) {
      for (int i = 0; i + (1 << j) <= (1 << lgsize); ++i) {
        int l = st[i][j - 1], r = st[i + (1 << (j - 1))][j - 1];
        st[i][j] = vec[l] <= vec[r] ? l : r;
      }
    }
    lookup.assign(vsize + 1, 0);
    for (int i = 2; i <= vsize; ++i) lookup[i] = lookup[i >> 1] + 1;
  }
  T query(int l, int r) {
    ++r;
    int lgsize = lookup[r - l];
    return min(vec[st[l][lgsize]], vec[st[r - (1 << lgsize)][lgsize]]);
  }
  int query_index(int l, int r) {
    ++r;
    int lgsize = lookup[r - l];
    T   lv = vec[st[l][lgsize]], rv = vec[st[r - (1 << lgsize)][lgsize]];
    if (lv < rv) return st[l][lgsize];
    else if (lv > rv) return st[r - (1 << lgsize)][lgsize];
    else return min(st[l][lgsize], st[r - (1 << lgsize)][lgsize]);
  }
};

class EulerTour {
  int num = 0;
  void et_dfs(const Graph &graph, const int v, const int p, const int dep) {
    tour.push_back(v);
    in[v] = num++;
    depth_tour.push_back(dep);
    depth[v] = dep;
    for (const auto &e : graph[v]) {
      if (e.dst == p) continue;
      et_dfs(graph, e.dst, v, dep + 1);
      tour.push_back(v);
      depth_tour.push_back(dep);
      ++num;
    }
    out[v] = num - 1;
  }

  public:
  vector tour, depth_tour, in, out, depth;
  EulerTour(void) {}
  EulerTour(const Graph &graph, const int v) { init(graph, v); }
  void init(const Graph &graph, const int v) {
    tour.clear();
    depth_tour.clear();
    in.assign(graph.size(), 0);
    out.assign(graph.size(), 0);
    depth.assign(graph.size(), 0);
    et_dfs(graph, v, -1, 0);
  }
};

class LowestCommonAncestor {
  class PM1RangeMinimumQuery {
    int block_size, block_num;
    vector vec, block_bit;
    vector<vector<vector>> lookup;
    SparseTable<pair<int, int>> st;

    public:
    PM1RangeMinimumQuery(void) {}
    void init(const vector &original_vecter) {
      vec = original_vecter;
      int vsize = vec.size();
      block_size = 0;
      while ((1 << block_size) < vsize) ++block_size;
      block_size = max(1, (block_size >> 1));
      while (vsize % block_size) {
        vec.push_back(vec.back() + 1);
        ++vsize;
      }
      block_num = vsize / block_size;
      vector<pair<int, int>> block_min(block_num, {INT_MAX, INT_MAX});
      for (int i = 0; i < vsize; ++i) block_min[i / block_size] = min(block_min[i / block_size], {vec[i], i});
      st.init(block_min);
      block_bit.assign(block_num, 0);
      for (int i = 0; i < block_num; ++i) {
        int left = block_size * i;
        for (int j = 0; j < block_size - 1; ++j) {
          if (vec[left + j] < vec[left + j + 1]) block_bit[i] |= (1 << j);
        }
      }
      int bit_all = 1 << (block_size - 1);
      lookup.assign(bit_all, vector<vector>(block_size, vector(block_size)));
      for (int b = 0; b < bit_all; ++b) {
        for (int i = 0; i < block_size; ++i) {
          int mini = 0, now = 0;
          for (int j = i + 1; j < block_size; ++j) {
            b&(1 << (j - 1)) ? ++now : --now;
            if (mini > now) {
              mini = now;
              lookup[b][i][j] = j - i;
            } else {
              lookup[b][i][j] = lookup[b][i][j - 1];
            }
          }
        }
      }
    }
    int query_index(int l, int r) {
      int lb = l / block_size, rb = r / block_size;
      int lbpos = l % block_size, rbpos = r % block_size;
      if (lb == rb) return l + lookup[block_bit[lb]][lbpos][rbpos];
      int lbmini = l, rbmini = r;
      if (lbpos != 0) {
        lbmini = l + lookup[block_bit[lb]][lbpos][block_size - 1];
        ++lb;
      }
      if (rbpos != block_size - 1) {
        rbmini = r - rbpos + lookup[block_bit[rb]][0][rbpos];
        --rb;
      }
      int mini = vec[lbmini] < vec[rbmini] ? lbmini : rbmini;
      if (lb <= rb) {
        pair<int, int> stpair = st.query(lb, rb);
        if (stpair.first < vec[mini]) mini = stpair.second;
      }
      return mini;
    }
  };
  PM1RangeMinimumQuery rmq;

  public:
  EulerTour et;
  LowestCommonAncestor(void) {}
  LowestCommonAncestor(const Graph &graph, const int v) { init(graph, v); }
  void init(const Graph &graph, const int v) {
    et.init(graph, v);
    rmq.init(et.depth_tour);
  }
  int query(const int a, const int b) {
    int l = et.in[a], r = et.in[b];
    if (l > r) swap(l, r);
    int idx = rmq.query_index(l, r);
    return et.tour[idx];
  }
};

Edges edges;
Graph graph;
int main(void) {
  int n;
  cin >> n;
  edges.resize(n - 1);
  rep (i, n - 1) {
    int x, y;
    cin >> x >> y;
    --x;
    --y;
    edges[i] = {x, y};
  }
  int q;
  cin >> q;
  vector<pair<int, int>> ab(q);
  rep (i, q) cin >> ab[i].first >> ab[i].second;
  edges_to_graph(graph, edges, n, false);
  LowestCommonAncestor lca(graph, 0);
  vector ans(q);
  rep (i, q) {
    int a = ab[i].first - 1, b = ab[i].second - 1;
    int v = lca.query(a, b);
    ans[i] = lca.et.depth[a] + lca.et.depth[b] - 2 * lca.et.depth[v] + 1;
  }
  rep (i, q) cout << ans[i] << "\n";
  return 0;
}

LCAを解こうとして確認できそうな問題を探したらこれが良さそうだった。
バグりまくってすごく時間かかった。
実装力が+2くらいされた。

いわゆるEuler Tree + ±1RMQの形。
記号だからかなんなのか、±1RMQを検索しようとしてもほとんど引っかからない。
他人のコードを見てなんとか理解した。
頑張って実装した結果確かに速いが、定数倍重いなぁという印象。
RMQ→LCAはもっと重そうだから普通にセグメントツリーとかで良いかなぁ。
LCAに帰着しない形でSparse Table使ってO構築(n)クエリO(1)で解くアルゴリズムもあるみたいだが、理解に頭を使うことに疲れた・・・。
また今度余裕ができたらそっちも試してみよう。