LCASQ - Lowest Common Ancestor
You are given a rooted tree and an ordered list of queries. Each query is specified by two nodes u and v and the answer to a query is the lowest common ancestor of u and v.
Recall that the Lowest Common Ancestor of two nodes is the node that is furthest from the root and also an ancestor of the two nodes. In this problem we use the convention that a node is in fact an ancestor of itself.
Input
The first line contains an integer N, the number of nodes in the tree (N ≤ 10000). Each of the next N lines 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. Nodes will be labeled from 0 to N-1. Following will be a number Q, the number of queries that will be asked (Q ≤ 10000). Each of the next Q lines will have two numbers u and v (0 ≤ u, v < N) which specify the parameters of that specific query.
The root of the tree will always be node 0.
Output
For each query output the answer on its own line. Answers should follow the same order as given in the input.
Example
Input: 3
2 1 2
0
0
3
1 2
1 1
2 2 Output: 0
1
2
hide comments
|
king_87arshia:
2024-07-19 20:03:17
i think if spoj wants to be famous for good problems these 800 rated problems should be erased from it |
|
yasser1110:
2021-07-23 13:24:58
Only difference here from the other LCA problem is node are unordered i.e. node 99 can have a descendant node 1. |
|
pankaj_m05:
2021-06-05 21:56:33
Sample OP lol |
|
yash_sharma115:
2021-03-22 10:32:38
Finding LCA using binary lifting would do the job. |
|
anshjain18:
2020-09-04 10:45:37
why novie approach wont work? |
|
tejameranaam:
2020-08-23 09:58:28
Novice approach won't work this time. Implement Binary lifting |
|
rraj001:
2017-05-30 11:11:30
Same as LCA :) |
| Added by: | Joshua Kirstein |
| Date: | 2014-10-20 |
| Time limit: | 12s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
RSS