LCA(最近公共祖先)
2022/9/3 23:22:46
本文主要是介绍LCA(最近公共祖先),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
lca,即最近公共祖先。最近公共祖先,顾名思义,就是树上两个点最近的祖先。
我们大体上有三个算法来搞。
第一个:\(O(nlogn)\)预处理,\(O(1)\)查询。
大体上是借用了rmq问题的思路(就是区间最大/小值)来处理。
将树上问题转化为区间问题。
void dfs(int rt,int d){ v[rt]=true;num[++t]=rt;first[rt]=t;dep[t]=d;//处理深度和dfs序 for(int i=head[rt];i;i=edge[i].next){ if(!v[edge[i].v]){ dis[edge[i].v]=dis[rt]+edge[i].w; dfs(edge[i].v,d+1); num[++t]=rt;dep[t]=d;//dfs序不解释 处理出每个节点控制的区间 } } } void st(){ for(int i=1;i<=t;i++)st[i][0]=i; for(int j=1;(1<<j)<=t;j++){ for(int i=1;i+(1<<j)-1<=t;i++){ int a=st[i][j-1],b=st[i+(1<<(j-1))][j-1]; if(dep[a]<dep[b])st[i][j]=a; else st[i][j]=b; } } }//就是普通st表的预处理 int rmq(int l,int r){ int k=0; while((1<<(k+1))<=r-l+1)k++; int a=st[l][k],b=st[r-(1<<k)+1][k]; if(dep[a]<dep[b])return a; return b; } int lca(int u,int v){ int x=first[u],y=first[v]; if(x>y)swap(x,y); return num[rmq(x,y)]; }
然后第二种:tarjan的离线算法。大体上借用了并查集来搞。
向上回溯法,没搜标记0,搜完标记2,开始搜但是没搜完标记1。
当一个节点搜完时把它和父亲合并,即每个节点都能指向它搜完的最上面的祖先。
void tarjan(int x){ v[x]=1; for(int i=head[x];i;i=edge[i].next){ if(!v[edge[i].v]){ tarjan(edge[i].v); merge(x,edge[i].v);//搜完儿子 合并 } } for(int i=0;i<ques[x].size();i++){ int y=ques[x][i],id=quesid[x][i];//离线处理关于x的每个问题 if(v[y]==2)lca[x][y]=find(y);//并查集 } v[x]=2; }
最后是第三种(也是最常用的之一):\(O(nlogn)\)预处理,\(O(logn)\)查询的倍增算法。而且超级短。
思路很简单,我们找到树上两个点的时候倍增地向上跳祖先,一直跳到lca。
int f[100010][21];//我曾经不知道多少次把这个写成20然后re void dfs(int rt,int d){ v[rt]=true;dep[rt]=d; for(int i=head[rt];i;i=edge[i].next){ if(!v[edge[i].v]){ f[edge[i].v][0]=rt; for(int j=1;j<=20;j++){ f[edge[i].v][j]=f[f[edge[i].v][j-1]][j-1]; } dfs(edge[i].v,d+1); } } } int lca(int x,int y){ if(dep[x]>dep[y])swap(x,y); for(int i=20;i>=0;i--){ if(dep[f[y][i]]>=dep[x]){ y=f[y][i]; } } if(x==y)return x; for(int i=20;i>=0;i--){ if(f[x][i]!=f[y][i]){ x=f[x][i];y=f[y][i]; } } return f[x][0]; }
这篇关于LCA(最近公共祖先)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升