Submission #1590979

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
class EulerTour {
public:
  int N, k;
  vector<int> g[100001]; // maxの頂点数は適宜変更
  vector<int> vs, id, depth;
 
  EulerTour (int N) : N(N), k(0), vs(2 * N - 1), id(N, -1), depth(2 * N - 1) {}
  EulerTour () {}
 
  void Init(int n) {
      N = n;
      k = 0;
      vs.resize(2 * N - 1);
      id.resize(N, -1);
      depth.resize(2 * N - 1);
  }
 
  void AddEdge(int u, int v) {
    g[u].push_back(v);
    g[v].push_back(u);
  }
 
  // v : vertex, d : depth, k : num
  void Dfs(int v, int d, int &k) {
    id[v] = k;
    vs[k] = v;
    depth[k++] = d;
    int size_ = g[v].size();
 
    for (int i = 0; i < size_; ++i) {
      if (id[g[v][i]] == -1) {
          Dfs(g[v][i], d + 1, k);
          vs[k] = v;
          depth[k++] = d;
      }
    }
  }
 
  // 根は頂点0としている
  void Solve(int root = 0) {
    Dfs(root, 0, k);
  }
};
 
template <typename T>
class SegmentTree {
private:
  int n;
  T _init;
  vector<T> seg;
 
  int size (int N) {
    int ret;
    for (ret = 1; ret < N; ret <<= 1);
    return ret;
  }
 
  T query(int a, int b, int k, int l, int r) {
    if (r <= a or b <= l) return _init;
    if (a <= l and r <= b) return seg[k];
 
    T vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
    T vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
    return min(vl, vr);
  }
 
public:
  SegmentTree (int N, T i = 0) : n(size(N)), seg(size(N) * 2, i), _init(i) {}
  SegmentTree () {}
 
  void Init(int N, T i) {
      n = size(N);
      seg.resize(size(N) * 2 - 1, i);
      _init = i;
  }
 
  void Update (int k, T val) {
    k += n - 1;
    seg[k] = val;
    while (k > 0) {
      k = (k - 1) / 2;
      // 適宜変更
      seg[k] = min(seg[k * 2 + 1], seg[k * 2 + 2]);
    }
  }
 
  // [l, r) 開区間であることに注意!!! ... [l, r]ならfind(l, r + 1)
  T Find(int l, int r) {
    return query(l, r, 0, 0, n);
  }
};
 
class LCA {
public:
    int N;
    EulerTour etour;
    SegmentTree<pair<int, int> > segtree;
 
    LCA() {}
    LCA(int N) : N(N), etour(N) {}
 
    void Init(int N) {
        etour.Init(N);
    }
 
    void AddEdge(int u, int v) {
        etour.AddEdge(u, v);
    }
 
    // LCA求める前の下準備
    void Preparation() {
        etour.Solve();
        segtree.Init(etour.k, {int(1e9+7), int(1e9+7)});
        for (int i = 0; i < etour.k; ++i) segtree.Update(i, {etour.depth[i], i});
    }
 
    int Lca(int a, int b) {
        if (etour.id[a] > etour.id[b]) swap(a, b);
        pair<int, int> lca = segtree.Find(etour.id[a], etour.id[b] + 1);
        return etour.vs[lca.second];
    }

    int Solve(int a, int b) {
        if (etour.id[a] > etour.id[b]) swap(a, b);
        int lca = Lca(a, b), da, db, dc;
        da = etour.depth[etour.id[a]];
        db = etour.depth[etour.id[b]];
        dc = etour.depth[etour.id[lca]];
        return (da + db - 2 * dc + 1);
    }
 
};
 
int N, x, y, q, a, b;
LCA lca;
 
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    cin >> N;
    lca.Init(N);
    for (int i = 0; i < N - 1; ++i) {
        cin >> x >> y;
        x--, y--;
        lca.AddEdge(x, y);
    }
 
    lca.Preparation();
 
    cin >> q;
    for (int i = 0; i < q; ++i) {
        cin >> a >> b;
        a--, b--;
        cout << lca.Solve(a, b) << endl;
    }
    return 0;
}

Submission Info

Judge Result