最近公共祖先（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

模板：时间复杂度nlogn

#include<iostream>

#include<cstdio>

using namespace std;

struct yyy{

       int t,

       nex;

}e[ * ];

int deepth[], fa[][], lg[], head[];

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] + ;

       fa[f][] = fath;

       for (int i = ; ( << i) <= deepth[f]; i++)

              fa[f][i] = fa[fa[f][i - ]][i - ];

       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]] - ];

       if (x == y)

              return x;

       for (int k = lg[deepth[x]]; k >= ; k--)

       if (fa[x][k] != fa[y][k])

              x = fa[x][k], y = fa[y][k];

       return fa[x][];

}

int n, m, s;//n节点，m查询，s边数

void init()

{

       scanf("%d%d%d", &n, &m, &s);

       for (int i = ; i <= n - ; i++)

       {

              int x, y;  scanf("%d%d", &x, &y);

              add(x, y); add(y, x);

       }

       dfs(s, );

       for (int i = ; i <= n; i++)

              lg[i] = lg[i - ] + ( << lg[i - ] == i);

}

int main()

{

       init();

       for (int i = ; i <= m; i++)

       {

              int x, y;  scanf("%d%d", &x, &y);

              printf("%d\n", lca(x, y));

       }

       return ;

}