Lowest Common Ancestor
Definition
The lowest common ancestor (LCA) of two nodes is their common ancestor farthest from the root. For convenience, we write \(\text{LCA}(v_1,v_2,\ldots,v_n)\) or \(\text{LCA}(S)\) for the lowest common ancestor of a set of nodes \(S=\{v_1,v_2,\ldots,v_n\}\).
Properties
Parts of this Properties section are translated from wcipeg, with modifications.
- \(\text{LCA}(\{u\})=u\);
- \(u\) is an ancestor of \(v\) if and only if \(\text{LCA}(u,v)=u\);
- if neither of \(u\) and \(v\) is an ancestor of the other, then they lie in two different subtrees of \(\text{LCA}(u,v)\);
- in a preorder traversal, \(\text{LCA}(S)\) comes before every element of \(S\); in a postorder traversal, it comes after all of them;
- the LCA of the union of two sets of nodes is the LCA of the two sets' LCAs, that is, \(\text{LCA}(A\cup B)=\text{LCA}(\text{LCA}(A), \text{LCA}(B))\);
- the LCA of two nodes always lies on the shortest path between them in the tree;
- \(d(u,v)=h(u)+h(v)-2h(\text{LCA}(u,v))\), where \(d\) is the distance between two nodes in the tree and \(h\) is the distance from a node to the root.
Algorithms
Naive algorithm
Procedure
Repeatedly take the deeper of the two nodes and move it up. Since this is a tree, the two nodes are bound to meet, and the node where they meet is the LCA. Alternatively, first move the deeper node up until the two are at the same depth, then move both up together; again they are bound to meet.
Properties
The naive algorithm preprocesses the whole tree with a DFS in \(O(n)\) time and answers a single query in \(\Theta(n)\) time. If the tree is random in some way, the running time depends on the expected height of such a random tree.
Binary lifting
Procedure
Binary lifting is the classic way to find the LCA; it improves on the naive algorithm. With a precomputed array \(\text{fa}_{x,i}\), the two pointers move quickly and make far fewer jumps. Here \(\text{fa}_{x,i}\) is the \(2^i\)-th ancestor of node \(x\); the array can be precomputed by a DFS.
Here is how the jumps are sped up:
The first phase brings the two pointers \(u\) and \(v\) to the same depth. Let \(y\) be the difference between their depths. The binary decomposition of \(y\) turns the \(y\) jumps into one jump for each 1 in the binary representation of \(y\).
The second phase tries each \(i\) from the largest down to \(0\) inclusive: if \(\text{fa}_{u,i}\not=\text{fa}_{v,i}\), set \(u\gets\text{fa}_{u,i},v\gets\text{fa}_{v,i}\). At the end, the LCA is \(\text{fa}_{u,0}\).
Properties
Binary lifting takes \(O(n \log n)\) time to preprocess and \(O(\log n)\) time per query.
You can also swap the two dimensions of the fa array so that the smaller one comes first: this causes fewer cache misses and makes the program faster.
Example
HDU 2586 How far away? Shortest path queries on a tree.
Find the LCA first and then apply property \(7\), or compute the answer directly while finding the LCA.
Reference code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 | |
Tarjan's algorithm
Procedure
Tarjan's algorithm is an offline algorithm. It uses a disjoint set union to keep track of an ancestor of each node. It works as follows:
- Read the input edges into an adjacency list and the query edges into a second adjacency list. A query edge is really a virtual edge that we add; for convenience, each query edge is added to the
queryEdgearray together with its reverse as it is read. - Run a DFS over the tree, using the
visitedarray to record which nodes have been visited. - This step relies on backtracking. When the DFS reaches a node, create a new set containing only that node. Once the DFS of the subtree rooted at one of its children has finished, merge the child's set into the current node's set and record in
ancestorthe shallowest node of the merged set, which is the current node. - When backtracking from a node, look at each query edge in
queryEdgethat starts there: if its other endpoint has already been visited, theancestorof the set containing that endpoint is the LCA of the two nodes, so store it as the LCA result of the query edge right away. - Finally, output the results.
Properties
Tarjan's algorithm has to initialize the disjoint set union, so preprocessing takes \(O(n)\) time.
The naive version of Tarjan's algorithm answers all \(m\) queries in \(O(m \alpha(m+n, n) + n)\) time, but Tarjan's algorithm has a larger constant factor than binary lifting. An \(O(m + n)\) implementation exists.
Note
It is not true that the disjoint set union used in the naive Tarjan LCA algorithm is special enough for a single call to find() to take amortized \(O(1)\) time.
The naive Tarjan implementation below runs in \(O(m \alpha(m+n, n) + n)\). If you need strictly linear time, see the 1983 paper by Gabow and Tarjan, which gives an \(O(m + n)\) method.
Implementation
Reference code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 | |
Reduction to RMQ using the Euler tour
Definition
Run a DFS on a tree and write down a node's index every time the search arrives at it, whether for the first time or when backtracking. The result is a sequence of length \(2n-1\) called the Euler tour of the tree.
Below, \(pos(u)\) denotes the position of the first occurrence of node \(u\) in the Euler tour (also called the Euler tour index of \(u\)), and \(E[1..2n-1]\) denotes the Euler tour itself.
Procedure
The Euler tour reduces the LCA problem to an RMQ problem in linear time: \(pos(LCA(u, v))=\min\{pos(k)|k\in E[pos(u)..pos(v)]\}\).
The equation is easy to understand: the walk from \(u\) to \(v\) must pass through \(LCA(u,v)\) but never through any of its ancestors. So the node with the smallest Euler tour index on the walk from \(u\) to \(v\) is \(LCA(u, v)\).
A DFS computes the Euler tour in \(O(n)\) time, and the tour has length \(O(n)\), so the LCA problem reduces in \(O(n)\) time to an RMQ problem of the same size.
Implementation
Reference code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | |
To find the LCA of a pair of nodes \((u, v)\), query the range \([\min\{pos[u], pos[v]\}, \max\{pos[u], pos[v]\}]\) and take the node that its minimum corresponds to.
With a sparse table for the RMQ, the algorithm does not support online updates; preprocessing takes \(O(n\log n)\) time and each LCA query takes \(O(1)\) time.
Reduction to RMQ using the DFS order
The Euler tour has length \(2n-1\), which makes the constant factors in time and space a little large. In fact, the DFS timestamps \(\operatorname{dfn}\) are enough to find the LCA.
Consider a pair of nodes \((u,v)\) and let \(d=\operatorname{LCA}(u,v)\). If \(u=v\), then \(d=u\); this is a special case to be handled separately. Otherwise, assume without loss of generality that \(\operatorname{dfn}(u) < \operatorname{dfn}(v)\), so that \(v\) cannot be an ancestor of \(u\). Unlike the Euler tour, the DFS order does not contain \(d\) in the range \((\operatorname{dfn}(u), \operatorname{dfn}(v)]\). But the range does contain the child of \(d\) that lies on the path from \(d\) to \(v\), whether or not \(u\) is an ancestor of \(v\). So it is enough to find a node of minimum depth in the range \([\operatorname{dfn}(u) + 1, \operatorname{dfn}(v)]\) (it need not be unique): its parent is the LCA. The range starts at \(\operatorname{dfn}(u) + 1\) because, if \(u\) is an ancestor of \(v\) and the range included \(u\), the node of minimum depth would be \(u\) itself, whose parent is not the LCA.
So finding the LCA is once again an RMQ problem.
To avoid storing depths and parents separately, store \(\operatorname{fa}(u)\) at position \(\operatorname{dfn}(u)\) of the DFS order, and compare two entries of this sequence by their timestamps. The entry with the smallest timestamp in the range \([\operatorname{dfn}(u) + 1, \operatorname{dfn}(v)]\) is then \(\operatorname{LCA}(u,v)\). The reason is that every node in this range is a proper descendant of \(d\), so the DFS timestamp of its parent is at least \(\operatorname{dfn}(d)\); and the minimum \(\operatorname{dfn}(d)\) is attained at a child of \(d\) inside the range, which exists by the discussion above.
The reduction from LCA to RMQ via the DFS order takes \(O(n)\) time; the total complexity depends on the RMQ method used. Here is a reference implementation with a sparse table, with \(O(n\log n)\) preprocessing and \(O(1)\) queries:
Reference implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | |
Heavy-light decomposition
The LCA is the node at the shallower of the two pointers once both have jumped onto the same heavy path.
Heavy-light decomposition takes \(O(n)\) time to preprocess and \(O(\log n)\) time per query, with a small constant factor.
Link Cut Tree
In a Link Cut Tree, if two consecutive access operations are applied to u and then to v, the node returned by the second access is the LCA of u and v.
Without operations such as link and cut, a single query on a Link Cut Tree takes \(O(\log n)\) time.
Standard RMQ
The reduction from LCA to RMQ via the Euler tour was described above; its bottleneck is the RMQ. If RMQ can be solved in \(O(n) \sim O(1)\), then so can LCA.
In the Euler tour, adjacent numbers differ by 1 or -1, so the \(O(n) \sim O(1)\) ±1 RMQ applies.
This takes \(O(n) \sim O(1)\) time and \(O(n)\) space, supports online queries, and has a large constant factor.
Example: Luogu P3379 [Template] Lowest Common Ancestor (LCA)
Reference code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 | |
Practice problems
References
This page is an unofficial English translation of the original OI Wiki page (revision 9bb3a8e6), machine-translated by Claude Fable 5.2 on 2026-11-16. It has been modified from the original by translation and may contain errors. It is not endorsed by OI Wiki.
Found a translation problem? Report it on GitHub.
Authors of the original page: 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, 24OI-bot, zirnc, Tiphereth-A, Chlero, c-forrest, not-exist, Plastic-time (full contribution history)
All content on this page is provided under the terms of CC BY-SA 4.0 and SATA; additional terms may apply.