LCA - Lowest Common Ancestor

no tags 

A tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree. - Wikipedia 

The lowest common ancestor (LCA) is a concept in graph theory and computer science. Let T be a rooted tree with N nodes. The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself). - Wikipedia

Your task in this problem is to find the LCA of any two given nodes v and w in a given tree T.

For example the LCA of nodes 9 and 12 in this tree is the node number 3.


The first line of input will be the number of test cases. Each test case will start with a number N the number of nodes in the tree, 1 <= N <= 1,000. Nodes are numbered from 1 to N. The next N lines each one will start with a number M the number of child nodes of the Nth node, 0 <= M <= 999 followed by M numbers the child nodes of the Nth node. The next line will be a number Q the number of queries you have to answer for the given tree T, 1 <= Q <= 1000. The next Q lines each one will have two number v and w in which you have to find the LCA of v and w in T, 1 <= v, w <= 1,000.

Input will guarantee that there is only one root and no cycles.


For each test case print Q + 1 lines, The first line will have “Case C:” without quotes where C is the case number starting with 1. The next Q lines should be the LCA of the given v and w respectively.


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

Case 1:

hide comments
javier_dlg96: 2018-04-14 00:44:12

For those with runtime errors, try setting maxN to something higher than what the problem states.

sherlock11: 2018-02-02 15:18:50

weak test case .................
no need for using log(N) query

bradyawn: 2018-01-28 03:18:33

@ipg_2015054 Assume 1 is the root. The problem intends that (in the picture) but doesn't explicitly state it

ipg_2015054: 2017-11-16 13:48:33

Can anyone tell me how the edges are undirected , as if they are then we can take any node as the root node and answer will differ according to the root node taken.

Bihan Sen: 2017-10-06 09:50:59

AC :)

Last edit: 2017-10-06 10:16:43
smso: 2017-08-18 18:34:30

I got WA because I neglect the 2 points:
1. "...we allow a node to be a descendant of itself..."
2. The edges are undirected.

triettt: 2017-08-09 04:34:56


anupamwadhwa: 2017-08-05 22:49:50

Weak test case..

vishesh_345: 2017-07-27 09:04:33

I am getting rte with memory usage of 2000M. Please Help. Using lca + rmq(sparse table)

mrinal_verma: 2017-07-25 21:41:25

can someone plz tell me what is wrong in my code , im using lca+rmq

Last edit: 2017-07-26 09:17:26

Added by:hossamyosef
Time limit:0.600s-1.113s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Resource:FCIS/ASU Local Contest 2013