地产网站建设公司,成都市建设局官方网站,wordpress顶部菜单函数,广西壮族自治区市场监督管理局一.LCA介绍 LCA通常指的是“最近共同祖先”#xff08;Lowest Common Ancestor#xff09;。LCA是一种用于解决树或图结构中两个节点的最低共同祖先的问题的算法。
在树结构中#xff0c;LCA是指两个节点的最近层级的共同祖先节点。例如#xff0c;考虑一棵树#xff0c;…一.LCA介绍 LCA通常指的是“最近共同祖先”Lowest Common Ancestor。LCA是一种用于解决树或图结构中两个节点的最低共同祖先的问题的算法。
在树结构中LCA是指两个节点的最近层级的共同祖先节点。例如考虑一棵树其中节点A是节点B和节点C的祖先而节点D是节点B和节点C的共同祖先但节点D不是最低层级的共同祖先。在这种情况下LCA就是节点D。
LCA算法在计算机科学中有广泛的应用例如在计算树的最近公共祖先、解决图的连通性问题、计算有向无环图DAG的最近公共祖先等方面。常见的LCA算法包括基于深度优先搜索DFS的算法、基于倍增法的算法和Tarjan算法等。
LCA算法的实现方式取决于所使用的数据结构和具体问题的要求。它可以通过预处理树结构计算和存储每个节点的深度或其他相关信息以加快查询的速度。LCA算法的时间复杂度通常为O(logN)或O(1)其中N是树或图中的节点数量。
总之LCA算法是解决树或图结构中两个节点最低共同祖先的问题的一种常见算法。 二.倍增法求LCA 倍增法Binary Lifting是一种常用的求解最低共同祖先LCA问题的算法。它通过预处理和存储每个节点的跳跃祖先以实现快速查询LCA的目的。下面是倍增法求解LCA的详细步骤 预处理对于每个节点v计算并存储它的第2^i个祖先其中i从0开始逐渐增加。这可以通过深度优先搜索DFS遍历树来完成。对于根节点其第2^i个祖先就是根节点本身。对于其他节点v其第2^i个祖先可以通过它的第2^(i-1)个祖先的第2^(i-1)个祖先来计算。 查询LCA给定两个节点u和v首先比较它们的深度假设u的深度大于v的深度。然后通过不断向上跳跃u的祖先使得u和v的深度相等。具体步骤如下 如果u和v的深度不相等将u向上跳跃到与v深度相等的位置。这可以通过从最高位开始逐渐减小的方式进行即从最大的i开始如果u的第2^i个祖先的深度大于等于v的深度则将u跳跃到第2^i个祖先。然后同时向上跳跃u和v直到它们的第一个公共祖先出现。这可以通过从最高位开始逐渐减小的方式进行即从最大的i开始如果u的第2^i个祖先和v的第2^i个祖先不相等则将u和v同时跳跃到它们的第2^i个祖先。最后u和v的第一个公共祖先就是LCA。
倍增法求解LCA的时间复杂度为O(logN)其中N是树中的节点数量。这是因为在查询LCA时每次跳跃都会将节点的深度减半直到找到LCA为止。
总结起来倍增法是一种通过预处理和存储节点的跳跃祖先来求解LCA问题的算法。它具有较低的时间复杂度并且适用于静态树结构即树结构不会发生变化的情况下。 三.题目
P3379 【模板】最近公共祖先LCA - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 四.代码
#includebits/stdc.h
#define maxn 500005
using namespace std;
int n,m,s; //点次数根节点
//链式前向星
int cnt0,head[maxn];
struct Edge{int u,v,next;
}edge[maxn1];
void add(int u,int v){edge[cnt](Edge){u,v,head[u]};head[u]cnt;
}
//建树
int depth[maxn],p[maxn][25];
void dfs(int u,int fa){p[u][0]fa;depth[u]depth[fa]1;for(int ihead[u];i;iedge[i].next){int vedge[i].v;if(vfa) continue; //防止套娃无线循环dfs(v,u); }
}
int lca(int x,int y){if(depth[x]depth[y]) swap(x,y);for(int j24;j0;j--){if(depth[x]-(1j)depth[y]){xp[x][j]; //往上走 }}//特判巧合if(xy) return x;//现在x和y深度差不多同时上升for(int j24;j0;j--){if(p[x][j]!p[y][j]){xp[x][j]; yp[y][j];}} return p[x][0];
}
int main(){cinnms;for(int i1;in;i){int u,v;cinuv;add(u,v);add(v,u);}dfs(s,0); //建树 //预处理 for(int j1;(1j)n;j){ //长度 2^jn for(int i1;in;i){p[i][j]p[p[i][j-1]][j-1];}} //输出答案LCAwhile(m--){int x,y;cinxy;coutlca(x,y)endl;} return 0;
} 五.卡住笔者的一个小问题 六.answer:
注意
找到p[x][j]!p[y][j]的时候并没有直接break;
而是赋值后继续也就是意味着结合我的疑问j再0再往上跳1步才结束
这时就成功到达pick点最后return p[x][0]即为LCA;
其实就妙在遍历中找到时赋值后继续遍历这就解决了LCA不在倍增数的情况
