「OI之路」04图论-3最近公共祖先lca

最近公共祖先lca的四种求法

倍增lca

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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];
}

树剖lca

时间复杂度 预处理n+询问logn
ps:
其实树剖是在线算法中最快的
因为log是最坏情况下的复杂度

然而我一般都选择倍增

tarjan+并查集lca

时间复杂度 预处理$O(n*\alpha(n) )$+询问1
这属于离线算法

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

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

st表lca

先求欧拉序,用st表存储编号,nlogn预处理后即可O(1)

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