LCA-最近公共祖先
LCA指的是树上两个节点的最近公共祖先
由于常常有求树上某条路径相关的一些问题，这时一般就需要用到LCA
求LCA有很多种方法，下面列举几种：暴力、倍增、Tarjan、树链剖分
暴力求LCA
原理：对于已知每个结点的父亲结点的树，要求 $x$ 和 $y$ 的LCA，首先让深度更深的结点，此处不妨设为 $y$，向上跳到与 $x$ 同样的深度，然后两个结点再同时往上跳，直至重合，这个重合的结点就是他们的LCA。
这种方法由于效率低下，一般不会使用（除非题目很水，这种方法的优点在于写起来简单），
此处仅给出部分参考代码：
int GetLCA(int x, int y) {
if (dep[x] > dep[y]) // 令y为更深的
swap(x, y);
while (dep[x] < dep[y])
y = fa[y]; // 让更深的y先往上跳到与x同样的深度
while (x != y) // 两者同时往上跳到LCA
x = fa[x], y = fa[y];
return x;
}
倍增算法求LCA
原理：上面提到，单纯的往上跳的方法缺点在于一个一个地跳，时间复杂度过高。那么对这个跳的过程，我们可以进行倍增优化，也就是一次跳不止一个结点，这样就可以将时间复杂度降到对数级。
具体实现细节：
倍增算法求LCA分为两个部分
一个是预处理，这部分会求出每个结点的 $1，2，4，8 \cdots$倍父亲结点是哪一个，具体实现时是
一个简单的 $DP$
另一个是查询部分，这一部分是查询 $x$ 与 $y$ 的LCA，这一部分的整体框架类似于上面的暴力版本的查询，首先是让更深的 $y$ 跳到与 $x$ 同样的深度，此处跳的长度是两者的深度差以内的最大的 $2$ 的某次幂，然后是 $x$ 与 $y$ 在同样的深度一起往上跳，跳的深度也是类似的 $2$ 的尽可能大的某次幂
参考代码：
int fa[500010][20]; // 存2的各个次方倍的父亲节点
int maxdepth, n;
int depth[500010];
void init() // 预处理部分
{
for (int k = 0; 1 << k <= maxdepth; ++k)
fa[1][k] = 0;
// 初始化根节点1号节点的父亲节点全为空
for (int k = 1; 1 << k <= maxdepth; ++k) // 倍增跳的深度
for (int i = 2; i <= n; ++i) // 对每个节点都预处理
fa[i][k] = fa[fa[i][k - 1]][k - 1];
/*当前节点的2^k父亲就是父亲节点的2^(k-1)父亲的2^(k-1)父亲 */
}
int find(int x, int y) // 查询部分
{
if (depth[x] > depth[y]) swap(x, y); // 令y为更深的
while (depth[y] > depth[x]) // 只要深度没有相同
y = fa[y][int(log(depth[y] - depth[x]) / log(2))];
// 让y一直往上尽可能大跨度地跳
if (x == y) return x;
for (int k = log(depth[x]) / log(2); k >= 0; --k) // 从最大跨度开始看
if (fa[x][k] != fa[y][k])
x = fa[x][k], y = fa[y][k];
// 两者同时往上尽可能大跨度地跳
return fa[x][0];
}
时间复杂度：预处理 $O(n\log n)$，查询 $O(\log n)$
例题： 【模板】最近公共祖先（LCA）
Solution:
#include <bits/stdc++.h>
const int MAXN = 500005;
struct Node {
int v;
int next;
};
int n, m, s;
int heads[MAXN];
Node pool[2 * MAXN];
int nn;
int dep[MAXN]; // 每个点的深度
int anc[MAXN][20]; // anc[i][j]表示i点的2^j之前祖先点
int lg2[MAXN]; // lg2[i]等于(log i) + 1
void dfs(int u, int father) {
dep[u] = dep[father] + 1;
anc[u][0] = father;
for (int i = 1; (1 << i) <= dep[u]; ++i) {
anc[u][i] = anc[anc[u][i - 1]][i - 1];
}
// for (int i = 1; i <= 20; ++i) {
// anc[u][i] = anc[anc[u][i - 1]][i - 1];
// }
for (int i = heads[u]; i; i = pool[i].next) {
if (pool[i].v != father) {
dfs(pool[i].v, u);
}
}
}
int lca(int x, int y) {
if (dep[x] < dep[y]) {
std::swap(x, y);
}
while (dep[x] > dep[y]) {
x = anc[x][lg2[dep[x] - dep[y]] - 1];
}
if (x == y) return x;
for (int i = lg2[dep[x]] - 1; i >= 0; --i) {
if (anc[x][i] != anc[y][i]) {
x = anc[x][i];
y = anc[y][i];
}
}
// for (int i = 19; i >= 0; --i) {
// if (anc[x][i] != anc[y][i]) {
// x = anc[x][i];
// y = anc[y][i];
// }
// }
return anc[x][0];
}
// 加边函数
void addEdge(int u, int v) {
pool[++nn].v = v;
pool[nn].next = heads[u];
heads[u] = nn;
}
int main() {
std::cin >> n >> m >> s;
for (int i = 0; i < n - 1; ++i) {
int a, b;
std::cin >> a >> b;
addEdge(a, b);
addEdge(b, a);
}
for (int i = 1; i <= n; ++i) {
lg2[i] = lg2[i - 1] + ((1 << lg2[i - 1]) == i);
}
dfs(s, 0);
for (int i = 0; i < m; ++i) {
int x, y;
std::cin >> x >> y;
std::cout << lca(x, y) << '\n';
}
return 0;
}
