## 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.

### 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```

 < Previous 1 2 3 4 5 6 7 8 9 10 11 Next > raka143: 2020-08-28 14:12:59 LCA using binary lifting works fine. Took me 0.05s. k_r_i_s_h_123: 2020-08-24 15:03:35 getting wrong answer using binary lifting .............HELP LINK TO MY CODE https://www.spoj.com/status/k_r_i_s_h_123/# junloveyin: 2020-08-22 16:03:42 @sknayak you should reset array after found all LCA of (u,v) . Last edit: 2020-08-22 16:04:02 sknayak: 2020-08-20 09:27:44 I am getting TLE using binary lifting and sparse table in c++. Can anyone help please? up_in_smoke: 2020-08-10 14:43:50 I am getting this error : runtime error (SIGABRT) and I've no idea how please help. Used RMQ + segment tree Last edit: 2020-08-10 14:44:18 csq31: 2020-08-06 18:45:41 rmb to swap(tin[u],tin[v]) when querying using rmq else you might get segfault robosapien: 2020-06-03 13:21:24 Naive LCA : 0.38s :) brandonbreyers: 2020-05-27 11:21:06 I am getting SIGABRT error by using euler tour +rmq pirate_joker1: 2020-05-25 09:03:26 Important: 1)Constraints are perfectly correct (value of N). 2)One tricky test when u==v then lca(u,v )=u. 3) we also have to print test case number("Case : ") i missed this XD; manimanimani: 2020-05-15 21:29:24 probably the best problem for learning LCA!