LCA 复健笔记
什么是 LCA
最近公共祖先/最深公共祖先，顾名思义，两个点的公共祖先中离它们最近/深度最大的那个。
怎么求 LCA
这里使用倍增优化算法，因为之前看不懂所以我觉得应该补一下（现在也看不懂。）。
暴力求 LCA
不停向上搜索，直到两点合为一点。
展开代码
int LCA(int x, int y) {
if(d[x] < d[y]) swap(x, y); // 保持 x 的深度大于等于 y
while(d[x] != d[y]) x = F[x];
while(x != y) x = F[x], y = F[y];
return x;
}
倍增优化
显然，在大部分使用 LCA 的情景中，上面的暴力做法会超时。
倍增是一个经常会使用到的优化（比如 \(ST\) 表），核心思想就是把搜索的步长从 \(1\) 变到 \(2^k\).
设 f[i][j] 代表节点 \(i\) 向上搜索 \(2^j\) 层后到达的点。有递推式：
f[i][j] = f[f[i][j - 1]][j - 1]
根据数学原理，从第 \(i\) 个点向上搜 \(2^{j - 1}\) 层后再搜 \(2^{j - 1}\) 层相当于搜了 \(2^j\) 层。
于是我们得到了搜索的底层逻辑：
将深度较大的一方上移，直到该方深度小于另一方，接着将两点一同上移直到两点只合为一点。
展开代码
inline int lca(ll x, ll y) {
if(d[x] < d[y]) swap(x, y);
for(int i = LogN; i >= 0; --i) if(d[f[x][i]] >= d[y]) x = f[x][i];
if(x == y) return x;
for(int i = l[n]; i >= 0; --i) if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
return f[x][0];
}
接下来思考如何初始化。
一个点的深度是它父亲节点的深度 \(+1\).
此外，根据刚才的递推式也可以计算出 \(f\) 数组的值。递推上界到 \(\log{n}\) 就可以了。
于是有递归初始化。
展开代码
void init(ll u, ll fa) {
d[u] = d[fa] + 1;
for(int i = 1; i <= LogN; ++i) {
if((1 << i) >= d[u]) break;
f[u][i] = f[f[u][i - 1]][i - 1];
}
for(int i = head[u]; i; i = nxt[i]) {
int v = to[i];
if(v == fa) continue;
f[v][0] = u;
init(v, u);
}
}
应用场景
你需要求两个（或多个）点的公共祖先，但值域很大。