LCA  Lowest Common Ancestor
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.
Input
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.
Output
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.
Example
Input: 1 7 3 2 3 4 0 3 5 6 7 0 0 0 0 2 5 7 2 7 Output: Case 1: 3 1
hide comments
harshiscoding:
20210123 15:13:42
@up_in_smoke ,use if(n===0) break 

princemishra:
20201231 18:35:09
even LCA with O(n) works and rooted at node 1 Last edit: 20201231 18:35:33 

wille_25:
20201229 13:48:57
the value of M is not really 999, its around 200 ..the problem setter should look at this ...i took the value 999 & total iteration using sparse table +RMQ is (N*M)=(1000*999) but it gives TLE ..take M=200 . Last edit: 20201229 13:49:26 

satyamkr118:
20201227 12:35:12
My 100th one!! 

s_tank00_:
20201027 09:24:47
why i m getting a tle please help here's my code


raka143:
20200828 14:12:59
LCA using binary lifting works fine. Took me 0.05s. 

k_r_i_s_h_123:
20200824 15:03:35
getting wrong answer using binary lifting .............HELP


junloveyin:
20200822 16:03:42
@sknayak you should reset array after found all LCA of (u,v) . Last edit: 20200822 16:04:02 

sknayak:
20200820 09:27:44
I am getting TLE using binary lifting and sparse table in c++. Can anyone help please? 

up_in_smoke:
20200810 14:43:50
I am getting this error : runtime error (SIGABRT) and I've no idea how please help. Used RMQ + segment tree

Added by:  hossamyosef 
Date:  20130513 
Time limit:  0.600s1.113s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  FCIS/ASU Local Contest 2013 