【模板】最近公共祖先(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

说明

对于 $30\%$ 的数据,$N\leq 10$,$M\leq 10$。 对于 $70\%$ 的数据,$N\leq 10000$,$M\leq 10000$。 对于 $100\%$ 的数据,$N\leq 500000$,$M\leq 500000$。 样例说明: 该树结构如下: ![](https://cdn.luogu.com.cn/upload/pic/2282.png) 第一次询问:$2, 4$ 的最近公共祖先,故为 $4$。 第二次询问:$3, 2$ 的最近公共祖先,故为 $4$。 第三次询问:$3, 5$ 的最近公共祖先,故为 $1$。 第四次询问:$1, 2$ 的最近公共祖先,故为 $4$。 第五次询问:$4, 5$ 的最近公共祖先,故为 $4$。 故输出依次为 $4, 4, 1, 4, 4$。