LCASQ - Lowest Common Ancestor

no tags 

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.


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.


For each query output the answer on its own line. Answers should follow the same order as given in the input.


2 1 2

1 2
1 1
2 2 

hide comments
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
Time limit:12s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64