C++ Coding Test Course, Finding the Lowest Common Ancestor 2

Problem Description

There is a tree consisting of N nodes and N-1 edges. Each node is numbered from 1 to N. Given two nodes A and B, the task is to find the Lowest Common Ancestor (LCA) of these two nodes. However, since the tree can be very large, an efficient algorithm needs to be used.

Input

  • The first line contains the number of nodes N (1 ≤ N ≤ 100,000).
  • The second line provides the N-1 edge information. Each edge is given in the form of “parent child.”
  • The third line consists of the number of queries Q (1 ≤ Q ≤ 100,000) for which A and B are given.

Example Input

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

Example Output

2
1
3

Solution Strategy

To efficiently find the Lowest Common Ancestor, we will use the following approach.

  • Representation of Tree Structure: The tree is represented using an adjacency list. Each node is connected to its parent and children, thus forming the tree.
  • Creating Depth and Parent Arrays using DFS: We use the Depth First Search (DFS) algorithm to determine the depth of each node and to record the parent nodes. This information is essential for finding the LCA.
  • Binary Lifting: To efficiently find the LCA, we use the binary lifting method (Fast LCA). The process involves aligning the depths of the two nodes and finding their common ancestor.

Implementation Steps

1. Creating Tree Structure

First, we build the tree based on the edge information. In this process, we define the relationship between parents and children and represent it through an adjacency list.

2. Generating Depth and Parent Arrays using DFS

Now, we need to record the depth and parent of each node using DFS. The depth indicates how far each node is from the root, and the parent information is crucial for finding the LCA in the next step.

3. Implementing LCA Function

We implement a function to find the Lowest Common Ancestor of two nodes using binary lifting. This function compares the depths of the two nodes and adjusts the depths if needed, subsequently finding their ancestors.

4. Processing Queries

For each query, we find and output the LCA of the given two nodes A and B.

Code Implementation

#include 
#include 
#include 
#include 

using namespace std;

const int MAX_N = 100000;
const int LOG = 17; // log2(100000) ≈ 16.61

int parent[MAX_N + 1][LOG + 1]; // Parent array
int depth[MAX_N + 1];            // Depth array
vector tree[MAX_N + 1];     // Tree in adjacency list format
int N;

void dfs(int node, int par, int d) {
    depth[node] = d;
    parent[node][0] = par;
    for (int i = 1; i <= LOG; i++) {
        parent[node][i] = parent[parent[node][i - 1]][i - 1];
    }
    
    for (int child : tree[node]) {
        if (child != par) {
            dfs(child, node, d + 1);
        }
    }
}

int lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);

    for (int i = LOG; i >= 0; i--) {
        if (depth[parent[a][i]] >= depth[b]) {
            a = parent[a][i];
        }
    }

    if (a == b) return a;

    for (int i = LOG; i >= 0; i--) {
        if (parent[a][i] != parent[b][i]) {
            a = parent[a][i];
            b = parent[b][i];
        }
    }

    return parent[a][0];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;
    for (int i = 0; i < N - 1; i++) {
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    dfs(1, 0, 0); // Root is 1
    int Q;
    cin >> Q;

    for (int i = 0; i < Q; i++) {
        int a, b;
        cin >> a >> b;
        cout << lca(a, b) << '\n';
    }

    return 0;
}

Conclusion

This problem helps understand the use of DFS and binary lifting methods to find the Lowest Common Ancestor. Learning various algorithms to process trees and enhancing coding skills will be greatly beneficial. Practicing different approaches to explore tree structures and find the LCA based on the given problem will be very useful for coding test preparation.