Lowest Common Ancestor

All submissions for this problem are available.
Read problems statements in Mandarin Chinese.
In a rooted tree, the lowest common ancestor (or LCA for short) of two vertices u and v is defined as the lowest vertex that is ancestor of both that two vertices.
Given a tree of N vertices, you need to answer the question of the form "r u v" which means if the root of the tree is at r then what is LCA of u and v.
Input
The first line contains a single integer N. Each line in the next N  1 lines contains a pair of integer u and v representing a edge between this two vertices.
The next line contains a single integer Q which is the number of the queries. Each line in the next Q lines contains three integers r, u, v representing a query.
Output
For each query, write out the answer on a single line.
Constraints
20 points:
 1 ≤ N, Q ≤ 100
40 points:
 1 ≤ N, Q ≤ 10^{5}
 There is less than 10 unique value of r in all queries
40 points:
 1 ≤ N, Q ≤ 2 × 10^{5}
Example
Input: 4 1 2 2 3 1 4 2 1 4 2 2 4 2 Output: 1 2
Explanation
 "1 4 2": if 1 is the root, it is parent of both 2 and 4 so LCA of 2 and 4 is 1.
 "2 4 2": the root of the tree is at 2, according to the definition, LCA of any vertex with 2 is 2.
Author:  tuananh93 
Editorial  http://discuss.codechef.com/problems/TALCA 
Tags  lca, ltime14, mediumhard, tree, tuananh93 
Date Added:  3072014 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 