<PREV Problem:
NEXT>
Solved by 148 users: ...
UserDateAttemptTimeCMSC
ethanhunt17 may 2011C++1001.86292 
chumbalov31 oct 2010C++1801.65309 
DAV08 apr 2010C++4101.38325 
sandler13 dec 2010C++5301.56335 
gchebanov20 oct 2010C++2501.63362 
chumbalov31 oct 2010C++1301.40363 
chumbalov19 oct 2010C++101.26366 
DAV30 jan 2010C++3801.37368 
RAVEman27 feb 2009C++201.28369 
DAV09 apr 2010C++4201.36370 
DAV30 jan 2010C++3601.32371 
JohnJones_00120 oct 2009C++601.77377 
ntoskrnl.dll11 apr 2010C++7601.79377 
Smailik19 dec 2010C++201.99378 
Wasltone02 dec 2007C101.22379 
Languages
C++
124
FPC
19
Java
4
C
4
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

LCA problem

Time limit = 4 second(s)

Memory limit = 40 Mb

Given a tree description your program should answer series of LCA-queries:

LCA(u,v) == lowest common ancestor for nodes $u$ and $v$.

Input

The first line contains number of edges $E$. Next $E$ lines contain edge descriptions. Each description is

 vertext_id parent_vertex_id

Root has id equal to 0.

E ≤ 400000.

Next line contains number of queries $M$. M ≤ 400000. Then $M$ line follow with LCA-queries descriptions. Each description is two vertex ids $u$ and $v$ delimited by space.

Output

Output $M$ lines with answers (verteces ids) to the given $M$ LCA-queries.

Input#1
10
1 0
2 1
3 1
4 2
5 2
6 3
7 3
8 6
9 7
10 7
4
8 10
2 5
4 5
6 9
Output#1
3
2
2
3

Author:
Tests and description by Vyacheslav Simonenko.
20 May 2007

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 210ms

SW soft NIX
ID = 3.236.97.49