第一行包含三个正整数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
模板：时间复杂度nlogn
#include<iostream> #include<cstdio> using namespace std; struct yyy{int t,nex; }e[2 * 500001]; int deepth[500001], fa[500001][22], lg[500001], head[500001]; int tot; void add(int x, int y) //邻接表存树 {e[++tot].t = y;e[tot].nex = head[x];head[x] = tot; } void dfs(int f, int fath) {deepth[f] = deepth[fath] + 1;fa[f][0] = fath;for (int i = 1; (1 << i) <= deepth[f]; i++)fa[f][i] = fa[fa[f][i - 1]][i - 1];for (int i = head[f]; i; i = e[i].nex)if (e[i].t != fath)dfs(e[i].t, f); } int lca(int x, int y) {if (deepth[x]<deepth[y])swap(x, y);while (deepth[x]>deepth[y])x = fa[x][lg[deepth[x] - deepth[y]] - 1];if (x == y)return x;for (int k = lg[deepth[x]]; k >= 0; k--)if (fa[x][k] != fa[y][k])x = fa[x][k], y = fa[y][k];return fa[x][0]; } int n, m, s;//n节点，m查询，s边数 void init() {scanf("%d%d%d", &n, &m, &s);for (int i = 1; i <= n - 1; i++){int x, y; scanf("%d%d", &x, &y);add(x, y); add(y, x);}dfs(s, 0);for (int i = 1; i <= n; i++)lg[i] = lg[i - 1] + (1 << lg[i - 1] == i); }int main() {init();for (int i = 1; i <= m; i++){int x, y; scanf("%d%d", &x, &y);printf("%d\n", lca(x, y));}return 0; }
