发现LCA问题求解方法挺多的啊…总结了几种经典的。
所有模板用的都是同一道模板题，\(1\le n,m \le 5 \times 10^5\) 。
树上倍增
算是比较传统的做法了。树上倍增，顾名思义就是在树上采用倍增的思想。暴力思想求LCA就是让两个点在树上爬直到爬到同一个点，而树上倍增就巧妙地优化了暴力，使得每次爬2的幂，按照一个十进制数一定能被一堆2的幂凑成的思想(见下图)，所以总是可以爬到任意距离。
因为任何一个十进制数都可以被表示为二进制数，而任何二进制数都由二的幂和0相加而得
几乎所有OI教科书上都是以此作为LCA的一种重要解法，毕竟容易理解。
代码：
#include <bits/stdc++.h>
#define MAXN 500010
#define MAXLOGN 20
using namespace std;
vector<int> G[MAXN];
int root = 1;
int parent[MAXLOGN][MAXN];
int depth[MAXN];
void dfs(int v, int p, int d) {
parent[0][v] = p;
depth[v] = d;
for (int i = 0; i < (int)G[v].size(); i++) {
if (G[v][i] != p) dfs(G[v][i], v, d + 1);
}
}
void init(int V) {
dfs(root, -1, 0);
for (int k = 0; k + 1 < MAXLOGN; k++) {
for (int v = 0; v <= V; v++) {
if (parent[k][v] < 0) parent[k + 1][v] = -1;
else parent[k + 1][v] = parent[k][parent[k][v]];
}
}
}
int lca(int u, int v) {
if (depth[u] > depth[v]) swap(u, v);
for (int k = 0; k < MAXLOGN; k++) {
if ((depth[v] - depth[u]) >> k & 1) {
v = parent[k][v];
}
}
if (u == v) return u;
for (int k = MAXLOGN - 1; k >= 0; k--) {
if (parent[k][u] != parent[k][v]) {
u = parent[k][u];
v = parent[k][v];
}
}
return parent[0][u];
}
int main() {
int n, m;
scanf("%d", &n);
for (int i = 0, a, b; i < n - 1; i++) {
scanf("%d%d", &a, &b);
G[a].push_back(b);
G[b].push_back(a);
}
init(n);
scanf("%d", &m);
for (int i = 0, a, b; i < m; i++) {
scanf("%d%d", &a, &b);
printf("%d\n", lca(a, b));
}
return 0;
}
RMQ
RMQ(Range Minium Query)，查询区间内最小的数，可以巧妙地利用在LCA问题中。考虑到是对树操作，我们一遍DFS求出所有点的DFS序，然后求两点的LCA就是求DFS序中两个点第一次出现的位置中的所有数的最小值。找到最小值后返回原点即可。
基于RMQ的算法可以采用Sparse Table，可以做到 \(O(n \log n)\) 建表， \(O(1)\) 查询，总的时间复杂度是\(O (n\log n + Q)\) ，其中 \(Q\) 是查询次数。当然了别的算法比如线段树等也可以实现，但因为ST好写并且便于面对海量查询，以ST作为模板。
因为写的时候没有写好，所以时间空间双重爆炸（但还是能过），其实不用三维数组的。代码：
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
vector<int> G[MAX_N];
int root, n, m, k;
int vs[MAX_N * 2 - 1];
int depth[MAX_N * 2 - 1];
int id[MAX_N];
int dp[MAX_N * 2][MAX_LOG_N][2];
int rmq(int l, int r) {
int bin = 0;
while ((1 << (bin + 1)) <= r - l + 1) bin++;
if(dp[l][bin][0] < dp[r - (1 << bin) + 1][bin][0]) {
return dp[l][bin][1];
}
else return dp[r - (1 << bin) + 1][bin][1];
}
void st_init() {
for(int i = 0; i < k; i++) {
dp[i][0][0] = depth[i];
dp[i][0][1] = i;
}
for(int j = 1; (1 << j) <= k; j++) {
for (int i = 0; i + (1 << j) - 1 < k; i++) {
if (dp[i][j - 1][0] < dp[i + (1 << (j - 1))][j - 1][0]) {
dp[i][j][0] = dp[i][j - 1][0];
dp[i][j][1] = dp[i][j - 1][1];
}
else {
dp[i][j][0] = dp[i + (1 << (j - 1))][j - 1][0];
dp[i][j][1] = dp[i + (1 << (j - 1))][j - 1][1];
}
}
}
}
void dfs(int v, int p, int d, int &k) {
id[v] = k;
vs[k] = v;
depth[k++] = d;
for (int i = 0; i < G[v].size(); i++) {
if (G[v][i] != p) {
dfs(G[v][i], v, d + 1, k);
vs[k] = v;
depth[k++] = d;
}
}
}
int lca(int u, int v) {
return vs[rmq(min(id[u], id[v]), max(id[u], id[v]))];
}
int main() {
scanf("%d", &n);
for (int i = 0, a, b; i < n - 1; i++) {
scanf("%d%d", &a, &b);
a--, b--;
G[a].push_back(b);
G[b].push_back(a);
}
dfs(0, -1, 0, k);
st_init();
scanf("%d", &m);
for(int i = 0, a, b; i < m; i++) {
scanf("%d%d", &a, &b);
a--, b--;
printf("%d\n", lca(a, b) + 1);
}
return 0;
}
Tarjan
Tarjan发明的算法实在太多了…这里讲的是他发明的关于求LCA的一个Tarjan算法。
Tarjan算法的巧妙之处在于它是面向询问的，对于每个询问利用并查集处理出它的LCA，因此Tarjan算法是离线的。
先看核心伪代码：
tarjan(u) {
vis[u] = true
for each query contains u:
as query(u, v), if vis[v] = true, ans[query(u, v)] = find(v)
for each son of u:
if vis[u.son] = false, tarjan(u), parent[v] = u
}
就只有简短几行，有两个地方要注意：1.要等所有询问和对儿子的递归调用完后，它的父亲才会声明当前节点为它的儿子。这是Tarjan算法的核心。2.对于每一个询问一定会有查询到的机会，因为总会有一个点vis变为true.
以上图为例：假如现在Tarjan函数访问到了 \(u\) 结点，我们通过对 \(u\) 的query的遍历（可能是vector，也可能是链表），找到了一个 \(v\) ，这时 \(v\) 还没被访问过，暂时不处理。\(tarjan(u\))处理完以后，\(parent[u]= y\) 的左儿子， \(y\) 的左儿子处理完以后， \(parent[] = y\) 。现在回到了 \(y\) 结点上，继续进行对儿子的遍历，遍历到了 \(x\) ， \(x\) 搜到了 \(v\) ， \(v\) 有一对询问 \((u, v)\) 。 \(u\) 是访问过的。所以 \(find(u)\) ，因为此时 \(parent[y]\) 仍然是 \(y\) （因为 \(y\) 还没有完成所有处理），所以成功找到它们的LCA，即为 \(y\) 。
代码（好像又写炸了，把 \(O(N + Q)\) 写出了 \(O(N\log N)\)的效果… ）：
#include <bits/stdc++.h>
#define MAXN 500000 + 10
using namespace std;
struct Node {
int val, num;
};
vector<int> G[MAXN];
vector<Node> Q[MAXN];
bool vis[MAXN];
int ans[MAXN], par[MAXN];
inline int find(int x) {
return x == par[x] ? x : x = find(par[x]);
}
void tarjan(int u) {
vis[u] = true;
for (int i = 0; i < (int)Q[u].size(); i++) {
int v = Q[u][i].val;
if (vis[v]) ans[Q[u][i].num] = find(v);
}
for (int i = 0; i < (int)G[u].size(); i++) {
int v = G[u][i];
if (!vis[v]) tarjan(v), par[v] = u;
}
}
int main() {
int n, m;
scanf("%d", &n);
for (int i = 0; i <= n; i++) {
par[i] = i;
}
for (int i = 0; i < n - 1; i++) {
int a, b;
scanf("%d%d", &a, &b);
a--, b--;
G[a].push_back(b);
G[b].push_back(a);
}
scanf("%d", &m);
for (int i = 0; i < m; i++) {
int a, b;
scanf("%d%d", &a, &b);
a--, b--;
Q[a].push_back((Node){b, i});
Q[b].push_back((Node){a, i});
}
tarjan(0);
for (int i = 0; i < m; i++) {
cout << ans[i] + 1 << endl;
}
return 0;
}
End of All
其实这三种算法优缺点都很明显：Tarjan最简单也最好写（只有40行），但是必须离线。 Sparse Table查询快并且可以在线，但是预处理有点慢。树上倍增方法则是一种折中——查询也慢预处理也慢。
当然了，LCA不可能出成裸题来让人做，肯定是作为一个关键的知识点包含在题目中。具体题目具体分析吧。