最近公共祖先（LCA）模板

全栈程序员-站长 • 2021年6月12日下午9:00 • 未分类 • 阅读 118

第一行包含三个正整数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：

模板：时间复杂度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;
}