LCA学习笔记
_JF_
·
·
个人记录
本篇讲详细介绍 LCA 的各种求法。
LCA 指最近公共祖先，即两个节点之间距离最近的父节点。
如图，5 和 4 的最近公共祖先是 1。
P3379 最近公共祖先
1.倍增
时间：O(n\log(n)+q\log(n))
对于这个东西，大致思路如下：
每次首先预处理出每个节点的深度，假设我们现在求 4 和 5 的最近公共祖先，我们的做法是从深度较深的点开始往上跳，即 5 跳到 3 ，这时候 3 和 4 再往上跳到达 1，即最近公共祖先。
但是这个时间复杂度可以达到 O(n)，于是，我们考虑倍增。即假设某一个结点要跳 7 层，那它只用跳 2^2+2^1+2^0 即可，这样，通过二进制，跳的时间可以优化到 \log(n)。
设 fa[i][j] 表示结点 i 的第 2^j 个祖先的编号。就有
fa[i][j]=fa[fa[i][j-1]][j-1]
```cpp
void dfs(int node ,int fath)
{
dep[node]=dep[fath]+1;
fa[node][0]=fath;
for(int i=1;(1<<i)<=dep[node];i++)
fa[node][i]=fa[fa[node][i-1]][i-1];
for(int i=0;i<g[node].size();i++)
{
int v=g[node][i];
if(v==fath)
continue;
dfs(v,node);
}
}
```
在查询 $x$ 和 $y$ 的最近公共祖先的时候，首先我们需要将较深的结点跳到和较浅的结点同一层，然后我们在按 $2^i$ 一个个尝试去跳。注意，如果跳到的节点相同，**可能跳过了LCA**，所以不取。
```cpp
void LCA(int x,int y)
{
if(dep[x]<dep[y])
swap(x,y);
int d=dep[x]-dep[y];
for(int i=0; i<=log2(n); i++)
if((1<<i)&d)
x=fa[x][i];
if(x==y)//跳完后的结点刚刚好是y，那么y就是x,y的最近公共祖先
return y;
for(int i=log2(n);i>=0;i--)
{
if(fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
}
return fa[x][0];
}
```
[$Code$](https://www.luogu.com.cn/record/93145449)
时间:5.17s。
## 2.ST表+欧拉序
时间：$(n\log(n)+q)
欧拉序，简而言之就是树的深搜，回溯的结点也需要标记。
拿最开始的图来说，他的欧拉序就是： 1,3,5,3,6,3,1,4,1。
对于我们要找的两个点的LCA，就是他们两个点（如果一个点出现多次，任取一个）之间的深度最小值。
由于每个节点的深度是静态的，所以我们可以使用 ST 表维护。注意，维护的是区间内最小值的点的编号。
不会的同学可以左转：ST表学习笔记
Code
时间：4.98s。
3. 树链剖分
时间：O(n+q \log(n))
树剖求LCA，就是让较深的节点不断的往上跳，直到两个节点都跳到同一条重链为止，这时候深度较小的那个点就是LCA。
Code
不会的同学左转 树剖学习笔记
时间：5.00s。
4.Tarjan
时间：O(n+m)
这是一个离线的方法，基于 dfs 和并查集。
我们设两个点的为 u，v ，lca(u,v)=d。
在 dfs 的时候，一定是从 d 开始，先查询到两点的某一点，再回来到另外个点。所以我们不可以确定哪个点可以先遍历，故存两次。
我们在每次遍历完 u 的子树后，就把他和他的子树加入到他父节点的集合之中，在查询的时候，lca 就是他们两者先遍历完的点的集合中的深度最小的结点。
Code
时间：5.99s （常数较大）
首选倍增，带 \log 过不了的情况下写 Targan
THE END