Lowest Common Ancestor (Basic Method)

The lowest common ancestor of vertices U and V is their deepest shared ancestor in a rooted tree. A vertex counts as its own ancestor, so LCA(U,U)=U, and if U is above V then LCA(U,V)=U. “Lowest” refers to depth, not numerical label. Unlike the unique undirected path, the LCA depends on the chosen root.

LCA appears in path distances, path aggregation, tree queries, and virtual-tree construction. The basic method moves through parent pointers one edge at a time. It is easy to prove and useful when there are few queries or the tree is shallow. It also prepares the exact reasoning that binary lifting later accelerates.

Prerequisites: Rooted Trees and Tree Representation; parent and depth arrays.

Build the idea

1. 1. Understand the shared part of two ancestor paths

   Take edges (1,2), (1,3), (2,4), (2,5), (3,6), (6,7), rooted at 1. Ancestors of 4 are 4,2,1; ancestors of 5 are 5,2,1. Their deepest common vertex is 2. For 4 and 7 the first shared vertex toward the root is 1. For 3 and 7 the answer is 3 itself.

   Ancestor chains cannot split again after meeting: from any vertex there is only one parent. Therefore the common ancestors form one upward chain, whose deepest member is well-defined. This structure makes synchronized climbing possible.

2. 2. Equalize depths first

   Suppose depth[U]>depth[V]. Replace U with parent[U] until depths match. Every removed vertex is strictly deeper than V, so it cannot be an ancestor of V and therefore cannot be their LCA. This shows that leveling does not skip the answer. In the example, query (4,7) has depths 2 and 3. Move 7 to 6, making both vertices depth 2.

   If the vertices become equal while leveling, that vertex is the answer. This covers the case where one query vertex is an ancestor of the other, including root queries.

3. 3. Climb both vertices together

   Once depths match, if U and V are different, replace both by their parents. They stay at equal depths. Their ancestor chains must meet by the root, and the first meeting is deepest because every previous pair was lower and distinct. Hence that meeting is exactly the LCA.

   For (4,7), leveling gives (4,6). Their parents are (2,3), still different. The next pair is (1,1), so LCA=1. For (4,5), no leveling is needed and one simultaneous step reaches (2,2). These examples show why climbing only one arbitrary side after leveling would lose the simple invariant.

4. 4. Convert LCA into a distance formula

   The unique path U→V climbs from U to L=LCA(U,V) and descends to V. Its length is (depth[U]−depth[L])+(depth[V]−depth[L]), or depth[U]+depth[V]−2*depth[L]. Query (4,7) has distance 2+3−0=5, following 4–2–1–3–6–7. Query (3,7) has distance 1+3−2=2.

   The formula uses depths from the same root as the LCA preprocessing. Although both depths and LCA may change after rerooting, the final undirected distance remains unchanged. This is a useful consistency check.

5. 5. Know the cost before choosing the method

   Build parent and depth once using BFS in O(N). A query makes at most a linear number of parent steps, so it costs O(H), where H is the rooted tree height and H≤N−1. On a balanced tree H is logarithmic; on a path it is linear. With Q queries, O(N+QH) may be too slow when N and Q are both large.

   The code returns LCA and distance for each query. It treats parent[root]=0 as a sentinel but never needs to climb above the root for valid input. All query labels must be valid vertices of the same connected tree. Binary lifting replaces long climbs by jumps without changing these definitions.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int lca(int u,int v,const vector<int>&parent,const vector<int>&depth){
    // Raise only deeper vertices: they cannot yet be shared ancestors.
    while(depth[u]>depth[v]){
        u=parent[u];
    }
    while(depth[v]>depth[u]){
        v=parent[v];
    }
    // At equal depth, climb together; their first meeting is the deepest shared ancestor.
    while(u!=v){
        u=parent[u];
        v=parent[v];
    }
    return u;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,root,queries;
    cin>>n>>root>>queries;
    vector<vector<int>>graph(n+1);
    for(int i=0;i<n-1;++i){
        int a,b;
        cin>>a>>b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    // Preprocess parent/depth once for the fixed root.
    vector<int>parent(n+1,0),depth(n+1,0);
    queue<int>q;
    q.push(root);
    while(!q.empty()){
        int v=q.front();
        q.pop();
        for(int next:graph[v]){
            if(next!=parent[v]){
                parent[next]=v;
                depth[next]=depth[v]+1;
                q.push(next);
            }
        }
    }
    while(queries--){
        int u,v;
        cin>>u>>v;
        int ancestor=lca(u,v,parent,depth);
        // The path climbs to the LCA and then descends to the other endpoint.
        int distance=depth[u]+depth[v]-2*depth[ancestor];
        cout<<ancestor<<' '<<distance<<'\n';
    }
}

Complexity analysis

Preprocessing: O(N) time and O(N) memory. Each LCA/distance query: O(H) time, where H is rooted height, and O(1) extra query space. Total for Q queries: O(N+QH), with O(NQ) worst-case query work on a path.

Example input and output

N root Q, followed by N−1 edges and Q lines U V. For each query output LCA(U,V) and distance(U,V) in edges.

Input

7 1 4
1 2
1 3
2 4
2 5
3 6
6 7
4 5
4 7
3 7
7 7

Output

2 2
1 5
3 2
7 0

Queries include siblings, vertices on separate branches, an ancestor/descendant pair, and identical vertices. Their distances are 2,5,2,0.

Practical applications

Unweighted path distances, ancestor checks, splitting a path into two upward sections, and a reference implementation for testing faster LCA methods. Use binary lifting when many queries make linear climbing too expensive.

Check your understanding

Why is it safe to raise only the deeper vertex while depths differ?

Put it into practice

Print the full path U→V for each query using the basic LCA and parent pointers.