学习笔记：图论-LCA
cyh_toby
·
·
个人记录
概念
对于有根树T的两个结点u、v，最近公共祖先 LCA(T,u,v) 表示一个结点x，满足x是u和v的祖先且x的深度尽可能大。在这里，一个节点也可以是它自己的祖先。
分析一：离线-tarjan
- 起初，每个点的并查集源是自己；在结束对一个点和其子树的遍历后，将其与其父亲合并。
- 搜索完一个点的所有子树后，检查与此点相关的询问，假设当前点为$u$，其询问的点为$v$，若发现$v$已经被搜索过($vis[v]==1$)，那么$LCA(u,v) = f[v]$//此处$f[v]$表示$v$的并查集源。
### 证明&实现：
见[ZJL_OIJR大大关于离线LCA的博客](https://segmentfault.com/a/1190000015145319?utm_source=index-hottest)
## 分析二：在线-倍增
倍增算法需要$O(NlogN)$的预处理，存下每个点的祖先信息，然后以每次$O(logN)$的时间复杂度查询。
- 预处理$step1$：声明数组$anc[N][log_2N]$，其中，$anc[i][j]$表示$i$号节点的第$2^j$个祖先编号（与$ST$表类似）。
- 预处理$step2$：我们用$dfs$遍历全图，同时记录深度。对于$∀u∈G$，$anc[u][0]=father[u]$，然后从当前点向上处理，即
```cpp
anc[u][i] = anc[anc[u][i-1]][i-1]
```
- 查询$step1$：假设询问的点为$x$和$y$。首先，我们令$x$成为深度较大的那个点(便于操作)，然后使$x$不停向上跳，直到与$y$深度相同。这时，**倍增**的优势就显现出来了：一层一层跳当然不会错，但是效率低，所以采用一次跳$2^i$格，并且$i$从大到小，每次都尽可能多地跳，这样就可以刚好找到并且复杂度由$O(N)$降为$O(logN)$了。
```cpp
for(int i = 19; i >= 0; i--) {
if(dep[x] - (1<<i) <= dep[y])
x = anc[x][i];
}
if(x==y) return x;//如果已经重合，就直接返回即可
```
- **注意:** 此处一定要记得特判，这种情况就相当于$y$就是$x$的祖先；如果不特判，继续如下操作则会出错。
- 查询$step2$：现在 $x$ 和 $y$ 已经在同一层，那么显然我们要把他俩一起向上跳，直到刚好重合（不多也不能少）。一起跳很容易实现，但怎么实现刚好重合呢？如果我们写$if(anc[x][i] == anc[y][i])$就往上跳，那很有可能会跳多，就是说跳到了 LCA 的上方。所以，我们应该把$==$改成$!=$，才能保证一直跳在 LCA 下方。这样运行结束后， LCA 就刚好是$x$和$y$的父亲了。
```cpp
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];
```
利用好倍增，查询就是$O(logN)$的时间复杂度了。
## 代码
```cpp
/**********************************
Problem: luogu - P3379 - 【模板】最近公共祖先(LCA)
State: Accepted
From: 【模板】
Algorithm: LCA
Author: cyh_toby
Last updated on 2020.6.16
**********************************/
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 5e5+5, M = 5e5+5;
#define gc getchar
int n, m, rt;
int g[N], v[2*M], nxt[2*M], tot;
int anc[N][20], dep[N];
inline int rd() {
int x = 0, f = 1;
char c = gc();
while (c < '0' || c > '9') {
if (c == '-')
f = -1;
c = gc();
}
while (c >= '0' && c <= '9') {
x = (x << 1) + (x << 3) + c - '0';
c = gc();
}
return x * f;
}
inline void add(int x, int y) {
v[++tot] = y, nxt[tot] = g[x], g[x] = tot;
return;
}
void dfs(int u, int fa, int depth) {
anc[u][0] = fa, dep[u] = depth;
for (int i = 1; (1<<i) <= depth; i++)
anc[u][i] = anc[anc[u][i-1]][i-1];
for (int i = g[u]; i; i = nxt[i])
if (anc[u][0] != v[i])
dfs(v[i], u, depth+1);
return;
}
inline int lca(int x, int y) {
if (dep[x] < dep[y])
swap(x, y);
int derta = dep[x] - dep[y];
for (int i = 0; (1 << i) <= derta; i++)//将 derta 二进制分解再进行处理
if (derta & (1 << i) )
x = anc[x][i];
if (x == y) return x;
int t = log2((double)dep[x]);
for (int i = t; i >= 0; i--)
if (anc[x][i] != anc[y][i])
x = anc[x][i], y = anc[y][i];
return anc[x][0];
}
int main()
{
n = rd(), m = rd(), rt = rd();
for (int i = 1; i <= n-1; i++) {
int x = rd(), y = rd();
add(x, y);
add(y, x);
}
dfs(rt, 0, 0);
for (int i = 1; i <= m; i++)
printf("%d\n", lca(rd(), rd()));
return 0;
}
```
可以丢个传送门[【模板】LCA](https://www.luogu.com.cn/problem/P3379)
## 小结
个人认为倍增会比 tarjan 更实用。
其实倍增重要的并不是算法，而是**倍增思路和技巧**，**切忌死搬硬套**。掌握了**倍增思想**可以更有助于破题。