问题引入
如果现在给你一棵树，要求求出任意两点之间的的最近公共祖先（LCA），你该怎么做呢？
树上最近公共祖先
朴素算法求LCA
这个想法很简单，就是把从根节点到两个节点的路径分别求出来，然后找出路径中离根节点最远的两边同时存在的点即可，时间复杂度最坏 O(N)，N是节点数。
复杂度证明 ：
找到路径是 O(N)（全图遍历），匹配的时候最劣情况 O(N)，树是一条链并且 u,v 是同一个叶子节点。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| vector<int> g[maxn];
vector<vector<int>> pth[maxn];
void dfs(int u,int fa) {
for (auto v:g[u]) {
if (v==fa) continue;
pth[v]=pth[u]; pth[u].push_back(u);
dfs(v,u);
}
}
int solve(int u,int v) {
int l=min(pth[u].size(),pth[v].size());
for (int i=0;i<l;i++) {
if (pth[u][i]!=pth[v][i]) {
if (i) return i-1;
else return -1;
}
}
}
void init() {
dfs(root,0);
}
|
当然，还有另一种想法，就是让两个点一直往他的父亲走，先让两个到同一层，然后一起往上跳跃，直到找到第一个不一样的，时间复杂度依旧是 O(N)。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| int fa[maxn];
int dep[maxn];
void dfs(int u,int _fa) {
fa[u]=_fa;
for (auto v:g[u]) {
if (v==_fa) continue;
dep[v]=dep[u]+1;
dfs(v,u);
}
}
int solve(int u,int v) {
if (dep[u]>dep[v]) swap(u,v);
while (dep[u]!=dep[v]) v=fa[v];
while (fa[u]!=fa[v]) u=fa[u],v=fa[v];
return fa[u];
}
void init() {
dep[root]=0;
dfs(root,-1);
}
|
倍增算法求LCA
每次查询 O(N) 显然不是我们想要的复杂度，于是考虑优化。
思想
根据第二种朴素算法，我们每次只能跳一步，这是这个算法的瓶颈，那我们能不能一步跳多一点呢？
首先，我们知道，任何一个数都可以表示成若干个不同的 2^k 的和（因为每个数都有一个二进制），所以我们每次跳一步可以换成每次向上跳 2^k 步，若干次后一定可以跳到同一层。
所以如果能在 O(1) 的时间内得到向上跳 2^k 步的点，我们就可以在 O(log N) 的时间内跳到同一层。
同理，现在到了同一层要一步一步往上找，因为往上跳找祖先也可以变成每次跳2的次方步。但是，有一个问题，现在我们不知道要跳多少层了，那该怎么办呢？
这时候我们可以从大往小枚举 k 的值（从小到大可能虽然可以跳到这个点，但是不是最优，比如应该跳 12 步，正确跳法是 8 和 4，但是从小往大会跳 1,2,4 然后发现 8 跳不了，于是炸了qwq），如果跳 2^k 次方步两边已经相同了，那就不能跳到这个点。
1
2
3
4
5
6
7
8
9
| 1
|
2
|
3
/ \
4 5
/
6
|
如图，求 5 和 6 去找公共祖先，先找到同一层 4 和 5，然后往上跳，因为从大到小枚举，所以跳 2 步的时候会跳到 2 这个点，虽然可以，但不是最优。
所以我们跳的时候要注意跳到的那个点不能是相等的，这样的话可以跳到最近共同祖先的下一个点，然后答案就是再往上走一步就可以了。
然后，我们还有一个问题，怎么求跳的点？还记得倍增吗，我们可以用它求解。
代码随之而出：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| const int maxn=1e5+10;
const int maxlog=30;
vector<int> g[maxn];
int lg[maxn];
int dep[maxn];
int fa[maxn][maxlog];
void dfs(int u,int _fa) {
fa[u][0]=_fa;
dep[u]=dep[_fa]+1;
for (auto v:g[u]) {
if (v==_fa) continue;
dfs(v,u);
}
}
void init(int n) {
dfs(1,0);
for (int j=1;j<maxlog;j++) {
for (int i=1;i<=n;i++) {
fa[i][j]=fa[fa[i][j-1]][j-1];
}
}
}
int LCA(int u,int v) {
if (dep[u]>dep[v]) swap(u,v);
for (int i=maxlog-1;i>=0;i--) {
if (dep[u]<=dep[fa[v][i]]) v=fa[v][i];
}
if (u==v) return u;
for (int i=maxlog-1;i>=0;i--) {
if (fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
}
return fa[u][0];
}
|
算一算时间复杂度，初始化是 O(N) (遍历 O(N)，倍增 O(N)，常数 30)跟之前一样，询问是 O(log N)，比之前快了好多~