Home => ProblemSet => 7.1-13:最近公共祖先（LCA）
1741: 7.1-13:最近公共祖先（LCA）
Time Limit: 2 Sec Memory Limit: 512 MB Submit: 0 Solved: 50[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]
Description
如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。
Input
第一行包含三个正整数 N,M,S，分别表示树的结点个数、询问的个数和树根结点的序号。
接下来 N−1 行每行包含两个正整数 x, y，表示 x 结点和 y 结点之间有一条直接连接的边（数据保证可以构成树）。
接下来 M 行每行包含两个正整数 a, b，表示询问 a 结点和 b 结点的最近公共祖先。
接下来 N−1 行每行包含两个正整数 x, y，表示 x 结点和 y 结点之间有一条直接连接的边（数据保证可以构成树）。
接下来 M 行每行包含两个正整数 a, b，表示询问 a 结点和 b 结点的最近公共祖先。
Output
输出包含 M 行，每行包含一个正整数，依次为每一个询问的结果。
Sample Input Copy
5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5
Sample Output Copy
4
4
1
4
4
HINT
样例说明：
第一次询问： 2,4 的最近公共祖先，故为 4。
第二次询问： 3,2 的最近公共祖先，故为 4。
第三次询问： 3,5 的最近公共祖先，故为 1。
第四次询问： 1,2 的最近公共祖先，故为 4。
第五次询问： 4,5 的最近公共祖先，故为 4。
故输出依次为 4, 4, 1, 4, 4。
数据范围：
对于 30% 的数据， N≤10， M≤10。
对于 70% 的数据， N≤10000， M≤10000。
对于 100% 的数据， N≤500000， M≤500000。
第一次询问： 2,4 的最近公共祖先，故为 4。
第二次询问： 3,2 的最近公共祖先，故为 4。
第三次询问： 3,5 的最近公共祖先，故为 1。
第四次询问： 1,2 的最近公共祖先，故为 4。
第五次询问： 4,5 的最近公共祖先，故为 4。
故输出依次为 4, 4, 1, 4, 4。
数据范围：
对于 30% 的数据， N≤10， M≤10。
对于 70% 的数据， N≤10000， M≤10000。
对于 100% 的数据， N≤500000， M≤500000。