【题目来源】
洛谷：P3379 【模板】最近公共祖先（LCA） - 洛谷
【题目描述】
如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。
【输入】
第一行包含三个正整数 \(N,M,S\)，分别表示树的结点个数、询问的个数和树根结点的序号。
接下来 \(N-1\) 行每行包含两个正整数 \(x, y\)，表示 \(x\) 结点和 \(y\) 结点之间有一条直接连接的边（数据保证可以构成树）。
接下来 \(M\) 行每行包含两个正整数 \(a, b\)，表示询问 \(a\) 结点和 \(b\) 结点的最近公共祖先。
【输出】
输出包含 \(M\) 行，每行包含一个正整数，依次为每一个询问的结果。
【输入样例】
5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5
【输出样例】
4
4
1
4
4
【算法标签】
《洛谷 P3379 最近公共祖先（LCA）》 #最近公共祖先LCA# #模板题# #O2优化#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 500005;
int n, m, s, a, b; // n: 节点数，m: 查询数，s: 根节点
vector<int> e[N]; // 邻接表存储树
int dep[N]; // 节点的深度
int fa[N][20]; // 倍增祖先表，fa[u][i]表示u的2^i级祖先// 深度优先搜索，预处理深度和祖先表
void dfs(int u, int father)
{// 计算当前节点的深度dep[u] = dep[father] + 1;// 初始化直接父节点fa[u][0] = father;// 预处理倍增祖先表for (int i = 1; i <= 19; i++)fa[u][i] = fa[fa[u][i-1]][i-1];// 遍历子节点for (int v : e[u])if (v != father) // 避免走回父节点dfs(v, u);
}// 求两个节点的最近公共祖先
int lca(int u, int v)
{// 第一步：将u和v调整到同一深度if (dep[u] < dep[v]) swap(u, v);// 将u向上跳，直到与v同深度for (int i = 19; i >= 0; i--)if (dep[fa[u][i]] >= dep[v])u = fa[u][i];// 如果此时u==v，说明v是u的祖先if (u == v) return v;// 第二步：u和v同时向上跳for (int i = 19; i >= 0; i--)if (fa[u][i] != fa[v][i]) // 如果祖先不同，就一起向上跳u = fa[u][i], v = fa[v][i];// 此时u和v的父节点就是LCAreturn fa[u][0];
}int main()
{// 输入树的信息cin >> n >> m >> s;// 读入n-1条边for (int i = 1; i < n; i++){int x, y;cin >> x >> y;e[x].push_back(y);e[y].push_back(x);}// 从根节点s开始DFS，预处理深度和祖先表dfs(s, 0);// 处理m个查询for (int i = 1; i <= m; i++){int a, b;cin >> a >> b;cout << lca(a, b) << endl; // 输出LCA}return 0;
}
【运行结果】
5 5 4
3 1
2 4
5 1
1 4
2 4
4
3 2
4
3 5
1
1 2
4
4 5
4