【模板】最近公共祖先(LCA)

题目描述

如题,给定一棵有根多叉树,请求出指定两个点直接最近的公共祖先。

输入输出格式

输入格式


第一行包含三个正整数N、M、S,分别表示树的结点个数、询问的个数和树根结点的序号。 接下来N-1行每行包含两个正整数x、y,表示x结点和y结点之间有一条直接连接的边(数据保证可以构成树)。 接下来M行每行包含两个正整数a、b,表示询问a结点和b结点的最近公共祖先。

输出格式


输出包含M行,每行包含一个正整数,依次为每一个询问的结果。

输入输出样例

输入样例 #1

5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5

输出样例 #1

4
4
1
4
4

说明

时空限制:1000ms,128M 数据规模: 对于30%的数据:N<=10,M<=10 对于70%的数据:N<=10000,M<=10000 对于100%的数据:N<=500000,M<=500000 样例说明: 该树结构如下: ![](https://cdn.luogu.org/upload/pic/2282.png) 第一次询问:2、4的最近公共祖先,故为4。 第二次询问:3、2的最近公共祖先,故为4。 第三次询问:3、5的最近公共祖先,故为1。 第四次询问:1、2的最近公共祖先,故为4。 第五次询问:4、5的最近公共祖先,故为4。 故输出依次为4、4、1、4、4。