一种新的LCA算法
_zyx2012
·
·
算法·理论
本文将介绍一种 LCA 算法，具有实现简洁、常数小的优势。
过程
预处理
需要维护以下信息：
什么？深度都不用维护？
是的就是这个意思。
我们通过一遍 dfs 算出所有信息。
但是 $to$ 这东西怎么搞？
~~先说点废话:~~ 任意子树中有且只有一条从某个点到根的路径覆盖了子树中所有没有 $to$ 的点。
看上去很逆天，来证明一下：
1. 如果一个点没有 $to$，显然，它的父亲也不可能有 $to$。
2. 由此可知，子树中没有 $to$ 的点组成的点集一定时若干条从某个点到子树根节点的路径所经过的点组成点集的并。
3. 有了前两条结论，我们已经可以很明显地发现子树中所有没有 $to$ 地点可以被若干条从某个点到根的路径完整地覆盖，现在来证明它可以只用 $1$ 条：
假设存在至少两条，取其中任意两条，设其中一条为 $u$ 到根，另一条为 $v$ 到根，这里假设 $sz_u \geq sz_v$，很明显，从子树根节点到 $u$ 和 $v$ 的路径上不存在有 $to$ 的点。
- 如果 $u$ 是 $v$ 的祖先，那你还留着 $u$ 干什么？
- 否则，令 $c=\operatorname{LCA}(u,v)$，可以发现 $sz_c \geq sz_u + sz_v + 1$，又由于 $sz_u \geq sz_v$，有 $sz_c \geq sz_v + sz_v + 1$，则 $c$ 可以是 $to_v$，这与“从子树根节点到 $v$ 的路径上不存在有 $to$ 的点”矛盾，证明到此完成。
这样，我们就可以 dfs 了。
废话少说，直接看代码：
```cpp
vector<int> sz(n + 1),to(n + 1),at(n + 1),f(n + 1);
int dftop = 0;
auto dfs = [&](auto &&self,int x,int y) -> int {
f[x] = y;
sz[x] = 1;
at[x] = ++dftop;//更新f、sz、at
int mxsz = 0,vv = x;
//不得不扯一下树链剖分LCA的内容了，在树剖中，查询复杂度为O(logn)的关键就在于每跳一条轻边子树大小至少*2，这里也用到了类似的原理，把儿子分为轻重儿子，由于sz[轻儿子]<=sz[重儿子]，轻儿子的子树中所有还没找到to[v]的点v，to[v]都被确认为x。
for (auto &i:a[x])
if (i != y){
int v = self(self,i,x);
sz[x] += sz[i];//更新sz
if (sz[i] > mxsz)
mxsz = sz[i],swap(vv,v);//重儿子是最后被更新的，如果重儿子由之前确认的点u变成i，则把u按照轻儿子的方式处理并把重儿子设置为i，否则把i按照轻儿子的方式处理。
for (;v != x;v = f[v])
to[v] = x;
}
for (;sz[vv] * 2 <= sz[x];vv = f[vv]) to[vv] = x;//处理重儿子
return vv;
};
```
## 查询
如果要查询点 $u$ 和 $v$ 的 LCA，则重复执行以下步骤：
1. 如果$sz_u>sz_v$，交换 $u$ 和 $v$。
2. 如果$at_v \leq at_u$ 且 $at_u \lt at_v+sz_v$，即 $v$ 是 $u$ 的祖先，结束。
3. 否则，$u:=to_u$。
结束后 $v$ 就是 LCA。
但是你凭什么说这样是对的？难道不会在第三步的时候跳多了跳到 LCA 的祖先上面去？
还真不会，证明：
- 令 $c$ 为 $u$ 和 $v$ 真实的 LCA。
- $sz_c \geq sz_u+sz_v+1$。
- $sz_u \leq sz_v$。
- $sz_c \geq sz_u+sz_u+1$，那 $to_u$ 一定不比 $c$ 浅，直接跳过去肯定是对的。
复杂度：由于每跳一次 $sz_u$ 至少会乘 $2$，复杂度为 $\mathcal{O}(\log n)$。
这个算法做[P3379](https://www.luogu.com.cn/problem/P3379)完整的代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
int main (){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int n,m,s;
cin >> n >> m >> s;
vector<vector<int>> a(n + 1);
for (int i = n;--i;){
int x,y;
cin >> x >> y;
a[x].push_back(y);
a[y].push_back(x);
}
vector<int> sz(n + 1),to(n + 1),at(n + 1),f(n + 1);
int dftop = 0;
auto dfs = [&](auto &&self,int x,int y) -> int {
f[x] = y;
sz[x] = 1;
at[x] = ++dftop;
int mxsz = 0,vv = x;
for (auto &i:a[x])
if (i != y){
int v = self(self,i,x);
sz[x] += sz[i];
if (sz[i] > mxsz)
mxsz = sz[i],swap(vv,v);
for (;v != x;v = f[v])
to[v] = x;
}
for (;sz[vv] * 2 <= sz[x];vv = f[vv]) to[vv] = x;
return vv;
};
dfs(dfs,s,0);
for (;m--;){
int x,y;
cin >> x >> y;
for (;;){
if (sz[x] > sz[y]) swap(x,y);
if (at[y] <= at[x]&&at[x] < at[y] + sz[y]) break;
x = to[x];
}
cout << y << '\n';
}
}
```
# 优劣势分析
## 优势
- 实现简洁、常数小、需要维护的信息少，实测中，在节点数和查询量相近时具有和树链剖分相近的速度。
- 相较于树链剖分，这个算法少一遍 dfs，在节点多查询少时理论上具有更优的性能。
## 劣势
- ~~逆天~~正确性不明显，需要复杂证明支撑。
- 树链剖分能够轻松支持各种扩展功能，这个算法不行。
~~都看到这了还不点个赞，~~
~~那还是人吗？~~