AIOJ

author:ouuan, Backl1ght, billchenchina, CCXXXI, ChickenHu, ChungZH, cjsoft, countercurrent-time, diauweb, Early0v0, Enter-tainer, EtaoinWu, H-J-Granger, H-Shen, Henry-ZHR, HeRaNO, hsfzLZH1, huaruoji, iamtwz, imp2002, Ir1d, kenlig, Konano, Lyccrius, Marcythm, Menci, NachtgeistW, PeterlitsZo, psz2007, shuzhouliu, SkqLiao, sshwy, SukkaW, therehello, TrisolarisHD, ttzztztz, vincent-163, WAAutoMaton, Hunter19019

Definition

LCA, short for Lowest Common Ancestor, is the common ancestor of two vertices that is farthest from the root. For convenience, we denote the LCA of a vertex set $S=\{v_1,v_2,\ldots,v_n\}$ by $\text{LCA}(v_1,v_2,\ldots,v_n)$ or $\text{LCA}(S)$ .

Properties

This Properties section was translated from wcipeg and modified.

$\text{LCA}(\{u\})=u$ ;
$u$ is an ancestor of $v$ if and only if $\text{LCA}(u,v)=u$ ;
If $u$ is not an ancestor of $v$ and $v$ is not an ancestor of $u$ , then $u,v$ lie in two different subtrees of $\text{LCA}(u,v)$ ;
In a preorder traversal, $\text{LCA}(S)$ appears before every element of $S$ , while in a postorder traversal, $\text{LCA}(S)$ appears after every element of $S$ ;
The LCA of the union of two vertex sets is the LCA of the LCAs of the two sets, that is, $\text{LCA}(A\cup B)=\text{LCA}(\text{LCA}(A), \text{LCA}(B))$ ;
The LCA of two vertices must lie on the shortest path between them;
$d(u,v)=h(u)+h(v)-2h(\text{LCA}(u,v))$ , where $d$ is the distance between two vertices in the tree and $h$ is the distance from a vertex to the root.

Methods

Naive algorithm

Process

At each step, let the deeper of the two vertices jump upward. Clearly, in a tree, the two vertices must eventually meet, and their meeting point is the LCA being sought. Alternatively, first lift the deeper vertex until the two vertices have the same depth, and then make them jump upward together; they must eventually meet as well.

Properties

The naive algorithm requires a DFS of the entire tree during preprocessing, with time complexity $O(n)$ and single-query time complexity $\Theta(n)$ . If the tree has a random shape, the time complexity depends on the expected height of such a random tree.

Binary lifting

Process

Binary lifting is the classic method for finding the LCA, and is an improved version of the naive algorithm. By preprocessing the $\text{fa}_{x,i}$ array, the cursor can move quickly, greatly reducing the number of jumps. $\text{fa}_{x,i}$ denotes the $2^i$ -th ancestor of vertex $x$ . The $\text{fa}_{x,i}$ array can be preprocessed using DFS.

Now let us see how to optimize these jumps: In the first stage of moving the cursors, we need to move vertices $u,v$ to the same depth. We can compute the difference between the depths of $u,v$ and call it $y$ . By decomposing $y$ into binary, we reduce the $y$ cursor jumps to a number equal to the number of 1s in the binary representation of $y$ . In the second stage, we loop from the largest $i$ down to $0$ (including $0$ ). If $\text{fa}_{u,i}\not=\text{fa}_{v,i}$ , then set $u\gets\text{fa}_{u,i},v\gets\text{fa}_{v,i}$ ; the final LCA is $\text{fa}_{u,0}$ .

Properties

The preprocessing time complexity of binary lifting is $O(n \log n)$ , and the time complexity of a single query is $O(\log n)$ . In addition, the two dimensions of the fa array can be swapped to put the smaller dimension first. This reduces the number of cache misses and improves program efficiency.

Example problem

HDU 2586 How far away? Shortest-path queries on a tree.

One can first compute the LCA and then solve the problem using Property $7$ . It is also possible to compute the answer directly while finding the LCA.

Reference code

#include <cstring>
#include <iostream>
#include <vector>

constexpr int MXN = 40005;
using namespace std;
vector<int> v[MXN];
vector<int> w[MXN];

int fa[MXN][31], cost[MXN][31], dep[MXN];
int n, m;
int a, b, c;

// DFS, preparing the lca algorithm. Takes two parameters: the DFS start vertex and its parent vertex.
void dfs(int root, int fno) {
  // Initialization: the 2^0 = 1-th ancestor is the parent vertex, and dep is one greater than the parent vertex.
  fa[root][0] = fno;
  dep[root] = dep[fa[root][0]] + 1;
  // Initialization of other ancestors: the 2^i-th ancestor is the 2^(i-1)-th ancestor of the
  // 2^(i-1)-th ancestor.
  for (int i = 1; i < 31; ++i) {
    fa[root][i] = fa[fa[root][i - 1]][i - 1];
    cost[root][i] = cost[fa[root][i - 1]][i - 1] + cost[root][i - 1];
  }
  // Traverse child vertices to perform DFS.
  int sz = v[root].size();
  for (int i = 0; i < sz; ++i) {
    if (v[root][i] == fno) continue;
    cost[v[root][i]][0] = w[root][i];
    dfs(v[root][i], root);
  }
}

// LCA. Compute the LCA vertex of x and y using binary lifting.
int lca(int x, int y) {
  // Make y deeper than x.
  if (dep[x] > dep[y]) swap(x, y);
  // Make y and x have the same depth.
  int tmp = dep[y] - dep[x], ans = 0;
  for (int j = 0; tmp; ++j, tmp >>= 1)
    if (tmp & 1) ans += cost[y][j], y = fa[y][j];
  // If y = x at this point, x and y are both their own ancestors.
  if (y == x) return ans;
  // Otherwise, find the first two vertices that are not their ancestors.
  for (int j = 30; j >= 0 && y != x; --j) {
    if (fa[x][j] != fa[y][j]) {
      ans += cost[x][j] + cost[y][j];
      x = fa[x][j];
      y = fa[y][j];
    }
  }
  // Return the result.
  ans += cost[x][0] + cost[y][0];
  return ans;
}

void Solve() {
  cin.tie(nullptr)->sync_with_stdio(false);
  // Initialize the ancestor array fa, cost, and depth dep.
  memset(fa, 0, sizeof(fa));
  memset(cost, 0, sizeof(cost));
  memset(dep, 0, sizeof(dep));
  // Read the tree: there are n vertices and m queries; each query asks for the LCA of two vertices.
  cin >> n >> m;
  // Initialize tree edges and edge weights
  for (int i = 1; i <= n; ++i) {
    v[i].clear();
    w[i].clear();
  }
  for (int i = 1; i < n; ++i) {
    cin >> a >> b >> c;
    v[a].push_back(b);
    v[b].push_back(a);
    w[a].push_back(c);
    w[b].push_back(c);
  }
  // Use DFS to compute the LCA.
  dfs(1, 0);
  for (int i = 0; i < m; ++i) {
    cin >> a >> b;
    cout << lca(a, b) << '\n';
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int T;
  cin >> T;
  while (T--) Solve();
  return 0;
}

Tarjan algorithm

Process

Tarjan's algorithm is an offline algorithm that uses disjoint-set union to record the ancestor of a vertex. Its procedure is as follows:

First read the input edges (the adjacency list) and the query edges (stored in another adjacency list). Query edges are virtual edges added for convenience; whenever a query edge is read, add it and its reverse to the queryEdge array.
Then perform a DFS traversal, using the visited array to record whether a vertex has been visited and parent to record the parent of the current vertex.
This involves backtracking. Whenever we visit a vertex, we regard the root of the tree rooted at this vertex as the vertex itself. After the DFS rooted at this vertex has been fully traversed, set the root of this tree to the parent of this vertex.
During backtracking, if the other endpoint of a queryEdge query edge starting at the current vertex has also been visited, update the LCA result for the query edge directly.
Finally, output the result.

Properties

Tarjan's algorithm requires initializing the disjoint-set union, so its preprocessing time complexity is $O(n)$ .

The naive Tarjan algorithm processes all $m$ queries in $O(m \alpha(m+n, n) + n)$ time, but its constant factor is larger than that of binary lifting. An $O(m + n)$ implementation exists.

Note

There is no such claim as ‘the disjoint-set union property used in the naive Tarjan LCA algorithm is special, so the amortized time complexity of a single call to find() is $O(1)$ ’.

The complexity of the naive Tarjan implementation below is $O(m \alpha(m+n, n) + n)$ . If strict linear time is required, refer to the 1983 paper by Gabow and Tarjan, which gives an $O(m + n)$ method.

Implementation

Reference code

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;

class Edge {
 public:
  int toVertex, fromVertex;
  int next;
  int LCA;
  Edge() : toVertex(-1), fromVertex(-1), next(-1), LCA(-1) {};
  Edge(int u, int v, int n) : fromVertex(u), toVertex(v), next(n), LCA(-1) {};
};

constexpr int MAX = 100;
int head[MAX], queryHead[MAX];
Edge edge[MAX], queryEdge[MAX];
int parent[MAX], visited[MAX];
int vertexCount, queryCount;

int find(int x) {
  if (parent[x] == x) {
    return x;
  } else {
    return parent[x] = find(parent[x]);
  }
}

void tarjan(int u) {
  parent[u] = u;
  visited[u] = 1;

  for (int i = head[u]; i != -1; i = edge[i].next) {
    Edge& e = edge[i];
    if (!visited[e.toVertex]) {
      tarjan(e.toVertex);
      parent[e.toVertex] = u;
    }
  }

  for (int i = queryHead[u]; i != -1; i = queryEdge[i].next) {
    Edge& e = queryEdge[i];
    if (visited[e.toVertex]) {
      queryEdge[i ^ 1].LCA = e.LCA = find(e.toVertex);
    }
  }
}

int main() {
  memset(head, 0xff, sizeof(head));
  memset(queryHead, 0xff, sizeof(queryHead));

  cin >> vertexCount >> queryCount;
  int count = 0;
  for (int i = 0; i < vertexCount - 1; i++) {
    int start = 0, end = 0;
    cin >> start >> end;

    edge[count] = Edge(start, end, head[start]);
    head[start] = count;
    count++;

    edge[count] = Edge(end, start, head[end]);
    head[end] = count;
    count++;
  }

  count = 0;
  for (int i = 0; i < queryCount; i++) {
    int start = 0, end = 0;
    cin >> start >> end;

    queryEdge[count] = Edge(start, end, queryHead[start]);
    queryHead[start] = count;
    count++;

    queryEdge[count] = Edge(end, start, queryHead[end]);
    queryHead[end] = count;
    count++;
  }

  tarjan(1);

  for (int i = 0; i < queryCount; i++) {
    Edge& e = queryEdge[i * 2];
    cout << "(" << e.fromVertex << "," << e.toVertex << ") " << e.LCA << endl;
  }

  return 0;
}

Converting to an RMQ problem with an Euler tour

Definition

During a DFS of a tree, record the number of a vertex every time it is reached, both on first visit and during backtracking. This produces a sequence of length $2n-1$ , called the Euler tour of the tree.

Below, let the position of the first occurrence of vertex $u$ in the Euler tour be denoted by $pos(u)$ (also called the Euler index of vertex $u$ ), and denote the Euler tour itself by $E[1..2n-1]$ .

Process

Given the Euler tour, the LCA problem can be converted to an RMQ problem in linear time, namely $pos(LCA(u, v))=\min\{pos(k)|k\in E[pos(u)..pos(v)]\}$ .

This equality is not difficult to understand: on the way from $u$ to $v$ , we must pass through $LCA(u,v)$ , but not through any ancestor of $LCA(u,v)$ . Therefore, the vertex with the smallest Euler-tour value encountered on the way from $u$ to $v$ is $LCA(u, v)$ .

Computing the Euler tour with DFS takes $O(n)$ time, and the Euler tour also has length $O(n)$ , so the LCA problem can be converted into an RMQ problem of the same scale in $O(n)$ time.

Implementation

Reference code

int dfn[N << 1], pos[N], tot, st[30][(N << 1) + 2],
    rev[30][(N << 1) + 2];  // rev stores the vertex number corresponding to the minimum depth

void dfs(int cur, int dep) {
  dfn[++tot] = cur;
  depth[tot] = dep;
  pos[cur] = tot;
  for (int i = head[t]; i; i = side[i].next) {
    int v = side[i].to;
    if (!pos[v]) {
      dfs(v, dep + 1);
      dfn[++tot] = cur, depth[tot] = dep;
    }
  }
}

void init() {
  for (int i = 2; i <= tot + 1; ++i)
    lg[i] = lg[i >> 1] + 1;  // Precompute lg instead of the library function log2 to optimize the constant factor
  for (int i = 1; i <= tot; i++) st[0][i] = depth[i], rev[0][i] = dfn[i];
  for (int i = 1; i <= lg[tot]; i++)
    for (int j = 1; j + (1 << i) - 1 <= tot; j++)
      if (st[i - 1][j] < st[i - 1][j + (1 << i - 1)])
        st[i][j] = st[i - 1][j], rev[i][j] = rev[i - 1][j];
      else
        st[i][j] = st[i - 1][j + (1 << i - 1)],
        rev[i][j] = rev[i - 1][j + (1 << i - 1)];
}

int query(int l, int r) {
  int k = lg[r - l + 1];
  return st[k][l] < st[k][r + 1 - (1 << k)] ? rev[k][l]
                                            : rev[k][r + 1 - (1 << k)];
}

When we need to query the LCA of a vertex pair $(u, v)$ , we only need to query the vertex represented by the minimum value on the interval $[\min\{pos[u], pos[v]\}, \max\{pos[u], pos[v]\}]$ .

If an ST table is used to solve the RMQ problem, the algorithm does not support online modification. Its preprocessing time complexity is $O(n\log n)$ , and the time complexity of each LCA query is $O(1)$ .

Heavy-light decomposition

The LCA is the vertex indicated by the cursor with smaller depth when the two cursors are moved onto the same heavy chain.

The preprocessing time complexity of heavy-light decomposition is $O(n)$ , and the time complexity of a single query is $O(\log n)$ , with a relatively small constant factor.

Link Cut Tree

In Link Cut Tree, suppose the points of two consecutive access operations are u and v, respectively. The point returned by the second access operation is the LCA of u and v.

Without link and cut operations, a single query using Link Cut Tree has time complexity $O(\log n)$ .

Standard RMQ

The discussion above showed how to convert the LCA problem into an RMQ problem using an Euler tour; the bottleneck is RMQ. If RMQ can be solved in $O(n) \sim O(1)$ time, then LCA can also be solved in $O(n) \sim O(1)$ time.

Since adjacent values in the Euler tour differ by either 1 or -1, we can use plus-minus one RMQ with $O(n) \sim O(1)$ complexity.

Time complexity is $O(n) \sim O(1)$ , space complexity is $O(n)$ , online queries are supported, and the constant factor is relatively large.

Example problem Luogu P3379【Template】Lowest Common Ancestor (LCA)

Reference code

#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;

constexpr int N = 5e5 + 5;

struct PlusMinusOneRMQ {  // RMQ
  // Copyright (C) 2018 Skqliao. All rights served.
  constexpr static int M = 9;

  int blocklen, block, Minv[N], F[N / M * 2 + 5][M << 1], T[N], f[1 << M][M][M],
      S[N];

  void init(int n) {  // initialization
    blocklen = std::max(1, (int)(log(n * 1.0) / log(2.0)) / 2);
    block = n / blocklen + (n % blocklen > 0);
    int total = 1 << (blocklen - 1);
    for (int i = 0; i < total; i++) {
      for (int l = 0; l < blocklen; l++) {
        f[i][l][l] = l;
        int now = 0, minv = 0;
        for (int r = l + 1; r < blocklen; r++) {
          f[i][l][r] = f[i][l][r - 1];
          if ((1 << (r - 1)) & i) {
            now++;
          } else {
            now--;
            if (now < minv) {
              minv = now;
              f[i][l][r] = r;
            }
          }
        }
      }
    }
    T[1] = 0;
    for (int i = 2; i < N; i++) {
      T[i] = T[i - 1];
      if (!(i & (i - 1))) {
        T[i]++;
      }
    }
  }

  void initmin(int a[], int n) {
    for (int i = 0; i < n; i++) {
      if (i % blocklen == 0) {
        Minv[i / blocklen] = i;
        S[i / blocklen] = 0;
      } else {
        if (a[i] < a[Minv[i / blocklen]]) {
          Minv[i / blocklen] = i;
        }
        if (a[i] > a[i - 1]) {
          S[i / blocklen] |= 1 << (i % blocklen - 1);
        }
      }
    }
    for (int i = 0; i < block; i++) {
      F[i][0] = Minv[i];
    }
    for (int j = 1; (1 << j) <= block; j++) {
      for (int i = 0; i + (1 << j) - 1 < block; i++) {
        int b1 = F[i][j - 1], b2 = F[i + (1 << (j - 1))][j - 1];
        F[i][j] = a[b1] < a[b2] ? b1 : b2;
      }
    }
  }

  int querymin(int a[], int L, int R) {
    int idl = L / blocklen, idr = R / blocklen;
    if (idl == idr)
      return idl * blocklen + f[S[idl]][L % blocklen][R % blocklen];
    else {
      int b1 = idl * blocklen + f[S[idl]][L % blocklen][blocklen - 1];
      int b2 = idr * blocklen + f[S[idr]][0][R % blocklen];
      int buf = a[b1] < a[b2] ? b1 : b2;
      int c = T[idr - idl - 1];
      if (idr - idl - 1) {
        int b1 = F[idl + 1][c];
        int b2 = F[idr - 1 - (1 << c) + 1][c];
        int b = a[b1] < a[b2] ? b1 : b2;
        return a[buf] < a[b] ? buf : b;
      }
      return buf;
    }
  }
} rmq;

int n, m, s;

struct Edge {
  int v, nxt;
} e[N * 2];

int tot, head[N];

void init(int n) {
  tot = 0;
  fill(head, head + n + 1, 0);
}

void addedge(int u, int v) {  // add an edge
  ++tot;
  e[tot] = Edge{v, head[u]};
  head[u] = tot;

  ++tot;
  e[tot] = Edge{u, head[v]};
  head[v] = tot;
}

int dfs_clock, dfn[N * 2], dep[N * 2], st[N];

void dfs(int u, int fa, int d) {
  st[u] = dfs_clock;

  dfn[dfs_clock] = u;
  dep[dfs_clock] = d;
  ++dfs_clock;

  int v;
  for (int i = head[u]; i; i = e[i].nxt) {
    v = e[i].v;
    if (v == fa) continue;
    dfs(v, u, d + 1);
    dfn[dfs_clock] = u;
    dep[dfs_clock] = d;
    ++dfs_clock;
  }
}

void build_lca() {  // like init
  rmq.init(dfs_clock);
  rmq.initmin(dep, dfs_clock);
}

int LCA(int u, int v) {  // compute LCA using RMQ; see the solution
  int l = st[u], r = st[v];
  if (l > r) swap(l, r);
  return dfn[rmq.querymin(dep, l, r)];
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m >> s;

  init(n);
  int u, v;
  for (int i = 1; i <= n - 1; ++i) {
    cin >> u >> v;
    addedge(u, v);
  }

  dfs_clock = 0;
  dfs(s, s, 0);

  build_lca();

  for (int i = 1; i <= m; ++i) {
    cin >> u >> v;
    cout << LCA(u, v) << '\n';
  }

  return 0;
}

Lowest Common Ancestor

Definition

Properties

Methods

Naive algorithm

Process

Properties

Binary lifting

Process

Properties

Tarjan algorithm

Process

Properties

Implementation

Converting to an RMQ problem with an Euler tour

Definition

Process

Implementation

Heavy-light decomposition

Link Cut Tree

Standard RMQ

Example problem Luogu P3379【Template】Lowest Common Ancestor (LCA)

Exercises