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
Abhinav92003:
2015-01-19 05:17:43
Solution accepted! Thanks for the question :) Last edit: 2013-12-12 14:08:55 |
|
NnN:
2015-01-19 05:17:43
got my mistake...working on it...isnt as simple as it seems.. Last edit: 2013-09-02 18:41:00 |
|
Amit RC:
2015-01-19 05:17:43
got WA for not writing case!!And spent 30 mins debugging code!!!....nd ya brute force does work here. |
|
Kevin Sebastian:
2015-01-19 05:17:43
pls tell the correct format of output..wen shud each line come |
|
Kevin Sebastian:
2015-01-19 05:17:43
@author please tell me what is wrong with my code getting WA |
|
Pragya Mishra:
2015-01-19 05:17:43
read the question carefully... ;) if u missd anything u will be in hell trouble..
|
|
$!:D:
2015-01-19 05:17:43
@Akash thnxx got AC :)
|
|
Ouditchya Sinha:
2015-01-19 05:17:43
Finally AC... :) Last edit: 2013-10-20 12:48:07 |
|
Akash:
2015-01-19 05:17:43
@$!:D I did it the same way u did..my solution is accepted..the only problem i found out is that u have printed "Case t" which always gives number of test cases and not the case number..and u have printed it before taking u and v input..try submitting it after correcting this error..and try compiling it with 4.0.0.8 bcos sometimes 4.3.2 gives compilation error or TLE but it compiles with another compiler Last edit: 2013-06-07 04:37:04 |
Added by: | hossamyosef |
Date: | 2013-05-13 |
Time limit: | 0.600s-1.113s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |
Resource: | FCIS/ASU Local Contest 2013 |