【最近公共祖先】 LCA 详解（倍增，trajan算法）

【最近公共祖先】 LCA

• 一、简单介绍 （Lowest Common Ancestors）
• 二、代码实现
• • 离线算法（离线）
  • • ①.插入函数
    • ②.并查集查找函数
    • ③.trajan 算法
    • Code
    • 算法小总结
  • 倍增法（在线）
  • • I.插入函数
    • II.dfs 函数
    • III. LCA查找函数
    • Code 2
    • 算法小总结
• 总结
• • 用途：
  • 题库
• 后记

一、简单介绍 （Lowest Common Ancestors）

在一棵二叉搜索树中，任意两个结点的最近公共祖先，是指以这两个结点为后代的深度最大的那个结点。需要通过比较两个结点的值，来判断它们在二叉搜索树中的位置关系。如果两个结点的值都小于当前结点的值，那么它们一定在当前结点的左子树中；如果两个结点的值都大于当前结点的值，那么它们一定在当前结点的右子树中；如果一个结点的值小于当前结点的值，另一个结点的值大于当前结点的值，那么当前结点就是它们的最近公共祖先。如果两个结点中有一个等于当前结点，那么当前结点也是它们的最近公共祖先。
对于有根树 $T$ 的两个结点 $u、v$ ，最近公共祖先 LCA (T,u,v) 表示一个结点$x$，满足 $x$ 是 $u$ 和 $v$ 的祖先且 $x$ 的深度尽可能大。在这里，一个节点也可以是它自己的祖先。

蒟蒻第一次画树，希望谅解

转载自 百度 最近公共祖先

二、代码实现

离线算法（离线）

①.插入函数

用邻接表存读入的一棵树，代码实现较好理解，解决代码：

struct Edge {int v,n;
}edge[N<<1];     //创建邻接表
int head[N],idx;	//邻接表存储树void connec(int x,int y) {edge[++idx].v=y;edge[idx].nxt=head[x];head[x]=idx;1
}

②.并查集查找函数

这里也不用多讲，就是普通并查集查找的使用：
如需深入了解，可以参考本博客用户的并查集文章…

int fa[N];		    //并查集数组
for(int i=1;i<=n;i++) fa[i]=i;    //并查集初始化 int findp(int x) {  //并查集查找根节点if(x==fa[x]) return x;return fa[x]=findp(fa[x]); 
}

③.trajan 算法

• ’$vis[i]：i号节点是否被访问过。$
• $fa[r]：r的祖先节点。$
• $res[i]：第i个询问的答案。$
• 看回上面开头的图，打个比例，如果我们要寻找 $A，C$的最近公共祖先，
  按照 $dfs$ 的先序遍历易知 $A$ 肯定是先被查询标记到的，并且 $fa[A]$ 在返回的过程中，指向了父亲节点的序号。
• 提前进行对于每个询问点的处理。

typedef pair<int,int>pll;  //第一个元素为节点编号，第二个元素为询问编号
vector <pll> vec[N];      //存储下来所有的询问 vec[x]：代表和x节点有关的询问，即第vec[x].secondfor(int i=1;i<=m;i++) {        //把 m次询问存下来 int x,y;scanf("%d%d",&x,&y);vec[x].push_back({y,i});vec[y].push_back({x,i});}

• 接下来，我们访问到 $C$ 节点，这时 $A,C$ 两个节点都被访问过了，我们只需找到关于询问 $C$ 节点的所有询问，$findp(y)$ 查询该节点（例子即 $A$ ）的祖先，即 $A,C$ 的最近公共祖先。
• 注意，由于 $root$ 的左节点还未返回，所以 f a r o o t l s o n = r o o t l s o n fa_{root_lson}=root_lson farootl​son​=rootl​son 即自己还指向自己，自己为自己的父亲。

void trajan(int u) {vis[u]=1;      //标记访问过 for(int i=head[u];i;i=edge[i].nxt) {int j=edge[i].v;if(!vis[j]) {trajan(j);fa[j]=u; } } for(int i=0;i<vec[u].size();i++) {int y=vec[u][i].first;int id_=vec[u][i].second;if(vis[y]) res[id_]=findp(y);}
}

Code

#include
using namespace std;
const int N=5e5+10;
typedef pair<int,int>pll;    //第一个元素为节点编号，第二个元素为询问编号
struct Edge {int v,n;
}edge[N<<1];
int head[N],idx;	//邻接表存储树
int fa[N];		    //并查集数组
int n,m,root;      	//分别表示节点个数，询问个数，根节点标号
vector <pll> vec[N];      //存储下来所有的询问 vec[x]：代表和x节点有关的询问，即第vec[x].second
int res[N];         //结果，把第i次询问的结果放进res[i]里面
bool vis[N];        //标记数组
void connec(int x,int y) {edge[++idx].v=y;edge[idx].nxt=head[x];head[x]=idx;
}
int findp(int x) {  //并查集查找根节点if(x==fa[x]) return x;return fa[x]=findp(fa[x]); 
}
void trajan(int u) {vis[u]=1;      //标记访问过 for(int i=head[u];i;i=edge[i].nxt) {int j=edge[i].v;if(!vis[j]) {trajan(j);fa[j]=u; } } for(int i=0;i<vec[u].size();i++) {int y=vec[u][i].first;int id_=vec[u][i].second;if(vis[y]) res[id_]=findp(y);}
}
int main() {scanf("%d%d%d",&n,&m,&root);for(int i=1;i<n;i++) {    //读入一棵树，用邻接表储存起来 int x,y;scanf("%d%d",&x,&y);connec(x,y);connec(y,x);} for(int i=1;i<=n;i++) fa[i]=i;    //并查集初始化 for(int i=1;i<=m;i++) {        //把 m次询问存下来 int x,y;scanf("%d%d",&x,&y);vec[x].push_back({y,i});vec[y].push_back({x,i});}trajan(root);      //调用trajan算法 for(int i=1;i<=m;i++) printf("%d\n",res[i]);return 0;
}

算法小总结

tarjan 的算法是离线算法，其中用到并查集，关键是 dfs 的主循环比较重要。
时间复杂度 ：时间复杂度为 O(n＋Q) ，$n$ 为数据规模，$Q$ 为询问个数。
由于用了 vector 动态数组，所以在时间运行效率上会低一点，但可以优化空间，相较于下面讲述的倍增算法，相当于空间换时间。

倍增法（在线）

I.插入函数

无论如何，我们还是要用到邻接表，废话不多说：

void connec(int x,int y) {edge[++idx].v=y;edge[idx].nxt=head[x];head[x]=idx;1
}

II.dfs 函数

$dep[u]：点前节点u到树根节点的深度（距离）。$
f [ u ] [ k ] ：节点 u 向根节点跳 1 k 个节点（保持在树的范围之内） . f[u][k] ：节点 u 向根节点跳 1^k 个节点（保持在树的范围之内）. f[u][k]：节点u向根节点跳1k个节点（保持在树的范围之内）.

• 注意：在此的跳跃$for$从小到大。

void dfs(int u,int fa) {dep[u]=dep[fa]+1;for(int i=head[u];i;i=edge[i].nxt) {    //遍历节点u的所有孩子 int j=edge[i].v;if(j==fa) continue;f[j][0]=u;for(int k=1;(1<<k)<=dep[u];k++)f[j][k]=f[f[j][k-1]][k-1];      //计算f数组 它最多到跟节点 dfs(j,u);     //继续往下搜 }
}

III. LCA查找函数

①.为了 $x$ 和 $y$ 的跳跃距可以同步跳到他们的最近公共祖先，我们先让两个节点跳到同样的深度，程序为了实现简便，使 $x$ 号节点在 $y$ 号节点的深度之下。

if(dep[x]<dep[y]) swap(x,y);

②.如果 $x=y$ , 所以 $y$ 是 $x$ 的祖先，直接返回 $y$。

if(x==y) return y;

③.否则 $x$ 和 $y$ 跳到其最近公共祖先的下一层。

if(f[x][i]!=f[y][i]) {     x=f[x][i];y=f[y][i];
}

④.最后只用再跳一步即 2 0 2^0 20 就到它们的最近公共祖先。

return f[x][0]; 

• 注意：在此的跳跃 $for$ 从大到小。
• 分析原因：我们此处的原理类似于二进制（蒟蒻的理解）
• 如 $9$ 的二进制为 ( 1001 ) B (1001)_B (1001)B​ ，如果我们从小到大选择，则会变成 $0111$，值为 $7$，最后导致错误。
• 同样的我们跳 $9$ 个节点，先跳 $8$ 个，再跳 $1$ 个。

int lca(int x,int y) {if(dep[x]<dep[y]) swap(x,y);    //让x成为深度最大的那个节点 for(int i=19;i>=0;i--)if(dep[f[x][i]]>=dep[y]) x=f[x][i];      //用倍增让x跳到和y同一层 if(x==y) return y;for(int i=19;i>=0;i--) {       //如果x跳过头了，就换一个小的i重跳 if(f[x][i]!=f[y][i]) {     //目标x和y跳到其最近公共祖先的下一层 x=f[x][i];y=f[y][i];}} return f[x][0];       //返回答案 
}

Code 2

#include
using namespace std;
const int N=5e5+10;
struct Edge {int v,nxt;
}edge[N<<1];
int n,m,x,y,root;       //分别表示节点个数，询问个数，根节点编号 
int head[N],idx;        //邻接表储存数 
int f[N][20]; 			//f(i,j)号节点往上跳2^j步的节点编号 
int dep[N];    			//节点i的深度 规定根节点的深度为 1 
void connec(int x,int y) {edge[++idx].v=y;edge[idx].nxt=head[x];head[x]=idx;
}
void dfs(int u,int fa) {dep[u]=dep[fa]+1;for(int i=head[u];i;i=edge[i].nxt) {    //遍历节点u的所有孩子 int j=edge[i].v;if(j==fa) continue;f[j][0]=u;for(int k=1;(1<<k)<=dep[u];k++)f[j][k]=f[f[j][k-1]][k-1];      //计算f数组  它最多到跟节点 dfs(j,u);     //继续往下搜 }
}
int lca(int x,int y) {if(dep[x]<dep[y]) swap(x,y);    //让x成为深度最大的那个节点 for(int i=19;i>=0;i--)if(dep[f[x][i]]>=dep[y]) x=f[x][i];      //用倍增让x跳到和y同一层 if(x==y) return y;for(int i=19;i>=0;i--) {       //如果x跳过头了，就换一个小的i重跳 if(f[x][i]!=f[y][i]) {     //目标x和y跳到其最近公共祖先的下一层 x=f[x][i];y=f[y][i];}} return f[x][0];       //返回答案 
}
int main() {scanf("%d%d%d",&n,&m,&root);for(int i=1;i<n;i++) {     //读入一棵树，用邻接表储存起来 scanf("%d%d",&x,&y);connec(x,y);connec(y,x);}dfs(root,0);       //计算每个节点的深度 for(int i=1;i<=m;i++) {scanf("%d%d",&x,&y);int tmp=lca(x,y);     //计算两个节点的lca printf("%d\n",tmp);}return 0;
} 

算法小总结

倍增算法是在线算法。
时间复杂度 ：时间复杂度为 O(nlogn) ，$n$ 为数据规模。
相较于刚刚所说的的trajan 算法，当然在运行效率上有很大优势。
建议多使用倍增算法，当忘了怎么打或爆空间下，才退而使用 trajan 算法。

总结

用途：

一、两个树上节点的最近公共祖先。
二、计算一个树上两个节点（$u\Rightarrow v$）之间的最短距离。
三、判断在树上是否能通过一条简单路径（即在树上找一条路径且不重复走一条边），使其经过给定点集中的所有点。
四、再一棵带权树上，通过枚举中间公共节点，找出两点之间的路径的极（最大、小）权值和。

题库

此处有配套练习，可以先浅浅练练 ，建议可以参考一下我的题单 洛谷【最近公共祖先】 ID：970993

后记

如有侵权，请联系一下我，说明情况，如属实，我会立即撤回文章！

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！