Submission #1590174

---

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, int i = 0) {
      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<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);
        for (int i = 0; i < etour.k; ++i) segtree.Update(i, etour.depth[i]);
    }

    // LCA求める前の下準備
    void Preparation() {
        etour.Solve();
        segtree.Init(etour.k, int(1e9 + 7));
        for (int i = 0; i < etour.k; ++i) segtree.Update(i, etour.depth[i]);
    }

    int Lca(int a, int b) {
        if (etour.id[a] > etour.id[b]) swap(a, b);
        int lca = segtree.Find(etour.id[a], etour.id[b] + 1);
        return (etour.depth[etour.id[a]] - lca) + (etour.depth[etour.id[b]] - lca) + 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.Lca(a, b) << endl;
    }
    return 0;
}

Submission Info

Judge Result