【OI之路】06树-5最近公共祖先LCA

最近公共祖先的四种求法

倍增lca

时间复杂度 预处理nlogn+询问logn
其实也没什么好说的,结合代码注释吧

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
//Zory-2017
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
//*******************全局常量*******************
const int MAXN=100000,MAXM=200000;
//*******************全局定义*******************
struct pt
{
int dep,hou;
}p[MAXN+10];
struct rod
{
int y,g;
}e[MAXM+10];
int bin[31];
//*******************实现*******************
int ln=0;
void ins(int x,int y)
{
ln++;
e[ln].y=y;
e[ln].g=p[x].hou;
p[x].hou=ln;
}
int f[MAXN+10][31];
void dfs(int x,int fa)
{
f[x][0]=fa;p[x].dep=p[fa].dep+1;//dep=bin[i]时只有f[x][i]
for(int i=1;bin[i]<=p[x].dep;i++) f[x][i]=f[f[x][i-1]][i-1];
for(int k=p[x].hou;k>0;k=e[k].g) if(e[k].y!=fa) dfs(e[k].y,x);
}
int LCA(int x,int y)
{
if(p[x].dep<p[y].dep) swap(x,y);
for(int i=30;i>=0;i--)
if(p[x].dep-p[y].dep>=bin[i])
x=f[x][i];//从高向低消除差距
if(x==y) return x;//y是x祖先
for(int i=30;i>=0;i--)
if(p[x].dep>=bin[i] and f[x][i]!=f[y][i])//防止跳过头
x=f[x][i],y=f[y][i];//一起向上跳
return f[x][0];
}
//*******************主函数*******************
int main()
{
bin[0]=1;for(int i=1;i<=30;i++) bin[i]=bin[i-1]<<1;
int n,m;scanf("%d%d",&n,&m);ln=0;
for(int i=1;i<=n-1;i++)
{
int x,y;scanf("%d%d",&x,&y);
ins(x,y);ins(y,x);
}
dfs(1,0);
while(m--)
{
int x,y;scanf("%d%d",&x,&y);
printf("%d\n",LCA(x,y));
}
}

树剖lca

时间复杂度 预处理n+询问logn
就是树剖跳tp的fa实现
不太常用,适用于已经打了树剖的情况

tarjan+并查集 lca

时间复杂度 预处理n+询问1
这属于离线算法

对于每个点,三种标记,0表示没访问过,
1表示访问过但没有回溯(x和x的祖先)
2表示访问且回溯过
那么对于x的每个询问(可以建立链表去枚举),如果y是1,则lca=y
如果y是2,则y向上的第一个【标记1】的节点就是lca

然后每次回溯的时候,把自己的块合并到父亲的块中
这就相当于把第一个【标记1】的节点指向父亲
那么每个询问的答案即findfa(y)

st表lca

用st表存储编号,预处理后即可O(1)

练习

Caioj1236模版
Caioj1237树上任意两点的距离

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/dc4.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%