Lowest Common Ancestor (LCA) Problem Statement

Understanding the concept of Lowest Common Ancestor (LCA) in graph theory and computer science is essential.

Consider a rooted tree ‘T’ containing ‘N’ nodes. The LCA between two nodes, ‘u’ and ‘v’, is the lowest node in the tree ‘T’ such that both ‘u’ and ‘v’ are descendants of this node (permitting a node to be its own descendant).

As an illustration, in a given tree, the LCA of nodes 5 and 8 is node 2, since node 2 lies on the path from node 5 to the root (node 1) and from node 8 to the root (node 1).

Example:

Input:

T = 1
N = 8
Edges: (1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7), (6, 8)
Q = 2
Queries: (5, 8), (4, 6)

Output:

2
1

Explanation:

- For nodes 5 and 8, the paths to the root are 5 → 2 → 1 and 8 → 6 → 3 → 1 respectively; LCA is 2.
- For nodes 4 and 6, paths are 4 → 2 → 1 and 6 → 3 → 1; LCA is 1.

Constraints:

• 1 <= T ≤ 5
• 1 <= N ≤ 105
• 1 <= Q ≤ 105
• 1 <= u, v ≤ N
• Time Limit: 1 sec

Note:

For each test case, the tree is rooted at node 1.