【洛谷P3379】【模板】最近公共祖先（LCA）

题目链接：P3379 【模板】最近公共祖先（LCA） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

LCA是什么？

LCA（Lowest Common Ancestors），即最近公共祖先，是指在有根树中，找出某两个结点u和v最近的公共祖先。

求解LCA的方法

朴素法，复杂度O(N)：先把两个点x和y跳到同一深度，然后同时往上跑，当x == y时返回x或y。当整棵树接近一条链状时，复杂度达到O(N)。

LCA倍增法，复杂度O(logN)，这也是我们要写的方法。

首先要预处理出每个点的所有祖先。可以用二进制分解，logN来算出。

倍增法利用了二进制的性质，每一个非负整数都可以由二进制表示出来，那么我们fa[x][i]表示x向上跳了2 ^ i个格子之后所在的位置。

不难发现fa[x][0]就是x的父节点（向上走2^0格），而fa[x][i] = fa[fa[x][i - 1]][i - 1]，也就是说x向上走2 ^ i格 = 向上走2 ^ (i - 1)，再走2 ^ (i - 1)，这里用到了动态规划的思想，因为在dfs递归到x时，x的父亲的fa是处理完了的。

处理完fa之后，我们就要求x和y的LCA了。

由朴素法提供的思路，我们先把x和y移动到同一深度。

设x的深度大于y（如果x深度小于y深度就交换x，y），从大到小（有点贪心的意思）遍历x的所有二进制位（假设为20位，基本够用），如果x向上移动后深度依然大于等于y就可以移动。最后一定能保证dep[x] == dep[y]。

举个例子，一开始dep[x] = 15, dep[y] = 2。x就向上走8 + 4 + 1步可以到y的深度。

当xy深度相同时，如果x==y就直接返回x或y。否则继续同时向上跑，如果x的2^i祖先和y的2^i祖先相等的话说明跑多了，如果不相等，说明还没到LCA，就可以往上跑，跑完之后可以保证x y一定位于LCA的下一层，那么LCA就是fa[x][0]或fa[y][0]。

完毕。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 5e5 + 10;
int N, M, S, T = 20;
int fa[maxn][25], dep[maxn];

vector<int> g[maxn];

void dfs(int x,int pre)
{
	dep[x] = dep[pre] + 1;
	fa[x][0] = pre;
	for(int i = 1;i <= T; ++ i)fa[x][i] = fa[fa[x][i - 1]][i - 1];
	for(auto &i : g[x])
	{
		if(i == pre)continue;
		dfs(i, x);
	}
}

int LCA(int x,int y)
{
	if(dep[x] < dep[y])swap(x, y);
	for(int i = T;i >= 0; -- i)if(dep[fa[x][i]] >= dep[y])x = fa[x][i];
	if(x == y)return x;
	for(int i = T;i >= 0; -- i)if(fa[x][i] != fa[y][i])x = fa[x][i], y = fa[y][i];
	return fa[x][0];
} 

signed main()
{
	scanf("%lld %lld %lld", &N, &M, &S);
	for(int i = 1;i < N; ++ i)
	{
		int x, y;scanf("%lld %lld", &x, &y);
		g[x].push_back(y);g[y].push_back(x);
	}
	dep[0] = -1;
	dfs(S, 0);//构造树 
	while(M --)
	{
		int x, y;scanf("%lld %lld", &x, &y);
		printf("%lld\n", LCA(x, y));
	}
	return 0;
}