Solved by 148 users: ...
UserDateAttemptTimeCMSC
ethanhunt`17 may 2011`C++1001.86292
chumbalov`31 oct 2010`C++1801.65309
DAV`08 apr 2010`C++4101.38325
sandler`13 dec 2010`C++5301.56335
gchebanov`20 oct 2010`C++2501.63362
chumbalov`31 oct 2010`C++1301.40363
chumbalov`19 oct 2010`C++101.26366
DAV`30 jan 2010`C++3801.37368
RAVEman`27 feb 2009`C++201.28369
DAV`09 apr 2010`C++4201.36370
DAV`30 jan 2010`C++3601.32371
JohnJones_001`20 oct 2009`C++601.77377
ntoskrnl.dll`11 apr 2010`C++7601.79377
Smailik`19 dec 2010`C++201.99378
Wasltone`02 dec 2007`C101.22379
 C++ 124 FPC 19 Java 4 C 4
` >  >  >  >  >  >  >  >  >  > `

## LCA problem

Time limit = 4 second(s)

Memory limit = 40 Mb

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

 © acm.mipt DevGroupThe page was generated in 170ms