Method lca_tree

code/graph/tarjan_olca.test.cpp:87–111

  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);