Class lca_tree

code/graph/tarjan_olca.test.cpp:80–130

}

struct lca_tree {
  int *label;
  int *orig;
  int *start;
  vector<ll> s;
  segment_tree st;

  lca_tree(int n, int root, vi *children) {
    label = new int[n];
    orig = new int[n];
    start = new int[n];
    memset(label, -1, n << 2);
    int at = 0;
    queue<int> Q;
    Q.push(root);
    label[root] = at++;
    while (!Q.empty()) {
      int cur = Q.front();
      orig[label[cur]] = cur;
      Q.pop();
      for (int i = 0; i < size(children[cur]); i++) {
        int nxt = children[cur][i];
        if (label[nxt] == -1) {
          label[nxt] = at++;
          Q.push(nxt);
        }
      }
    }

    seq(children, root);
    st = segment_tree(s);
  }

  void seq(vi *c, int r) {
    start[label[r]] = size(s);
    s.push_back(label[r]);
    for (int i = 0; i < size(c[r]); i++) {
      seq(c, c[r][i]);
      s.push_back(label[r]);
    }
  }

  int lca(int a, int b) {
    a = label[a];
    b = label[b];
    int x = start[a],
      y = start[b];
    if (x > y) swap(x, y);
    return orig[st.query(x, y).x];
  }
};

void test() {
  int tests = 100;