命题描述
(lca) ((Lowest) (Common) (Ancestors))
对于有根树 (T) 的两个结点 (u、v)，最近公共祖先 (lca(u,v)) 表示一个结点 (x)，满足 (x) 是 (u) 和 (v) 的祖先且 (x) 的深度尽可能大。
显然，一个节点也可以是它自己的祖先。
算法思想
我们假设一棵树，如下:
如何求出节点9和节点4的最近公共祖先呢？其实无非就是找到这两个节点到根的路径的第一个相交点。
（因为是一棵树，所以不可能出现环，也就是说每个点到根的路径是唯一的。
然后，求出这个相交点就很简单了嘛，你只需要先走一遍节点9或节点4走到根的路径。
然后标记一下走过的点，再跑一遍另外一个点到根的路径，如果遇到了之前的标记，就代表找到lca了。
模拟一遍例子：
4 -> 3 -> 1 (vis[4] = true, vis[3] = true, vis[1] = true)
9 -> 5 -> 3 (vis[3] == true, finish)
交换顺序。。
9 -> 5 -> 3 -> 1 (vis[9] = true, vis[5] = true, vis[3] = true, vis[1] = true)
4 -> 3 (vis[3] == true, finish)
code 1
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 10005;
int fa[MAXN];
// fa[i]表示i节点的父亲节点
bool vis[MAXN];
// vis[i]表示i节点是否在x节点到根的路径上
// 即标记
void Make_Tree(int n) { // 建树
for(int i = 1; i <= n; i++)
fa[i] = i;
return ;
}
void dfs(int i) {
vis[i] = true; // 标记当前节点
if(fa[i] == i) // 到达根节点了
return ;
dfs(fa[i]); // 继续往上
}
int lca(int i) {
if(vis[i] == true) // 如果遇到第一个被标记的点，表示找到lca了，返回
return i;
lca(fa[i]);
}
int main() {
int n, m;
// 这棵树有n个节点
// m次询问
scanf("%d %d", &n, &m);
// 输入一棵树
Make_Tree(n);
for(int i = 1; i <= n - 1; i++) {
int x, y;
scanf("%d %d", &x, &y);
fa[y] = x;
}
for(int i = 1; i <= m; i++) {
memset(vis, 0, sizeof vis); // 初始化
int x, y;
scanf ("%d %d", &x, &y);
// 表示询问x，y两个节点的最近公共祖先
dfs(x);
// 跑一遍x到根
printf("%d
", lca(y));
// 再跑y到第一个被标记过的节点
}
return 0;
}
不过很显然，上面的思路时间复杂度很高（（
于是我们考虑优化。
对于上面的算法思路，我们是让两个点中的一个先走，然后另一个再走。那如果我们让它们一起走呢？
两个点同时往上走，如果这两个点第一次相遇了，则它们相遇的地方就是它们的最近公共祖先。
不过这样还不够，因为如果两个点不在同一个深度上，会出现深度深的节点永远追不上深度浅的节点的尴尬情况。
所以我们需要进行一些预处理，先把深度深的节点往上走到和另一个节点深度一样，然后就可以一起往上走啦。
还是刚刚那个图。。
9 -> 5 -> 3
4 -> 3 (u == v, finish)
code 2
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n, q, m;
const int MAXN = 20005;
vector<int> s[MAXN];
// 动态数组存树（（邻接表
void add(int x, int y) {
s[x].push_back(y);
}
int fa[MAXN], dep[MAXN];
// fa[i]表示i节点的父亲节点，dep[i]表示i节点的深度
void init() { // 建树初始化
for(int i = 1; i <= n; i++)
fa[i] = i;
}
void Make_Tree(int x) { // 建树
for(int i = 0; i < s[x].size(); i++){
int y = s[x][i];
fa[y] = x;
dep[y] = dep[x] + 1; // 这里需要再维护一个深度
Make_Tree(y);
}
}
int lca(int x, int y) {
if(dep[x] > dep[y]) swap(x, y);
// 保证x的深度一定比y的深度浅
while(dep[x] < dep[y])
y = fa[y];
// 现在已经保证了深度的大小关系，所以将深度深的往上爬即可
while(x != y) {
x = fa[x];
y = fa[y];
// 一起往上走
}
return x;
}
int main() {
scanf("%d %d %d", &n, &m, &q);
// 这棵树有n个节点
// m次询问
// 顺便限制一下树的根节点为q
for(int i = 1; i < n; i++) {
int u, v;
scanf("%d %d", &u, &v);
add(u, v); // 加入一条树上的边
}
dep[q] = 1;
Make_Tree(q); // 建树
while(m--) {
int x, y;
scanf("%d %d", &x, &y); // 询问
printf("%d
", lca(x, y));
}
return 0;
}
你以为到这里就完了？
其实上面的代码还可以进行优化！
根据上面的思路，我们是让两个点到达同一深度后，慢慢往上走，且每次走一步。
一次走一步真的很傻，于是我们考虑能否让这两个点一次性走很多步，同时不会直接跳过 (lca)。
我们可以维护一个点的二的幂次方倍祖先，也就是保存一个它的父亲，它父亲的父亲，它爷爷的爷爷。
这样每次走的时候就相当于可以一次性走二的幂次方步了！
并且这样走的话一定能找到 (lca)， 并且不会跳过。因为每个数都能拆成几个二的幂次方相加。所以当前点到 (lca) 的距离也一定能。
// fa[x][i]表示x节点的2^i倍节点
for(int i = 20; i >= 0; i--) { // 循环极值不一定是20，因题而异，这里写20是因为2^20已经够大了
if(fa[x][i] != fa[y][i]) {
// 如果不等于，表示在lca之前
// 如果等于，则一定在lca之后（没问题吧
x = fa[x][i];
y = fa[y][i];
// 往上走
}
}
return fa[x][0];
有没有觉得很奇怪，为什么要从大往小枚举？
我们来分类证明一下。
如果 (lca) 在 (2^i) 倍节点之上，即走了 (2^i) 步后没到 (lca)，这种情况好像顺序不影响答案。。。
那如果走了 (2^i) 步之后错过了 (lca)，显然我们需要调整为走更小的步数。那么这个从大到小的顺序就产生作用了。
最后我们就一定能求出两个点 (x, y)，它们的一倍祖先是同一个节点。
同理，我们也可以用这样的思路来调整两个节点的深度大小。
for(int i = 20; i >= 0; i--)
if(dep[fa[x][i]] >= dep[y])
x = fa[x][i];
不过，为什么往上走的条件从等于变成了大于等于？
毕竟是每次走2的幂次方倍步嘛，所以我们每次考虑走不走是依据的能否更接近另外一个点的深度，而不是等于另外一个点的深度。
最后再在一开始初始化一下每个点的2的幂次方祖先。
for(int j = 0; j <= 20; j++)
for(int i = 1; i <= n; i++)
fa[i][j + 1] = fa[fa[i][j]][j];
// 初始化依据：当前节点的爷爷节点就是这个节点的父亲节点的父亲节点
// 同理。。。
完整代码。
code 3
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n, q, m;
const int MAXN = 20005;
vector<int> s[MAXN]; // 邻接表建树
void add(int x, int y) {
s[x].push_back(y);
}
int fa[MAXN][25], dep[MAXN];
void init() {
for(int j = 0; j <= 20; j++)
for(int i = 1; i <= n; i++)
fa[i][j + 1] = fa[fa[i][j]][j];
// 初始化2的幂次方祖先
}
void Make_Tree(int x) {
for(int i = 0; i < s[x].size(); i++){
int y = s[x][i];
if(y == fa[x][0]) continue; // 下一个点是当前点的父亲，显然不能走过去，避免重复
fa[y][0] = x;
dep[y] = dep[x] + 1;
// 维护深度
Make_Tree(y);
}
}
int lca(int x, int y) {
if(dep[x] < dep[y]) swap(x, y);
// 调整相对深度
for(int i = 20; i >= 0; i--)
if(dep[fa[x][i]] >= dep[y]) // 将深度深的往上走
x = fa[x][i];
if(x == y) return x;
for(int i = 20; i >= 0; i--) {
if(fa[x][i] != fa[y][i]) {
// 一起往上走
x = fa[x][i];
y = fa[y][i];
}
}
return fa[x][0];
}
int main() {
scanf("%d %d %d", &n, &m, &q);
for(int i = 1; i < n; i++) {
int u, v;
scanf("%d %d", &u, &v);
add(u, v);
add(v, u);
}
dep[q] = 1;
Make_Tree(q);
init();
while(m--) {
int x, y;
scanf("%d %d", &x, &y);
printf("%d
", lca(x, y));
}
return 0;
}