\(0.\) 问题简介
有一棵树, 告诉你它的节点数 n, 根的编号 s 以及所有的边. 求 m 次询问, 每次查询给定任意两个树上节点的最近公共祖先.
数据范围:\(n,m\leq 10^5\)
\(1.\) 暴力
暴力很好理解, 就是一个一个往他的父亲节点跳. 学过并查集的同学们应该都知道, 一个一个往上跳这种做法是很浪费时间的, 所以针对这道题, 也会 \(tle\)
\(2.\) 优化(倍增)
看标题也都会知道一定是倍增
针对并查集, 我们采取的优化办法是路径压缩求解. 但很明显,\(LCA\)要求的是当前节点到根的路径上的某个信息, 每次查询还有可能不同.
所以这种办法对于 \(LCA\)问题不可行.
让后便有了以下名言
出题人说:"数据要大!"
于是便有了倍增.
关于倍增, 在 "RMQ 问题与 ST 表" 这篇博客中有初步介绍.
对于这种问题, 我们可以事先统计出每个节点第 \(2^k\ (k\in N_+)\)辈父亲节点, 然后便可以大大减少时间.
统计树上信息(\(dfs\))
(个人认为 \(dfs\)比较容易理解且代码简洁)
首先引入一个重要的定义:\(fa\)数组
其中:\(fa_{i,j}\)代表第 \(i\)号结点第 \(2^j\)辈祖先
所以可得
\[ fa_{i,j}=fa_{fa_{i,j-1},j-1}\]
这样, 我们就可以方便地得到 \(fa_{i,j}\)
- inline void dfs(int now,int pre){//now 为当前节点, pre 为其直接父亲节点, 也就是上一个被搜到的节点
- fa[now][0]=pre;
- depth[now]=depth[pre]+1;// 记录深度
- for(rg int i=1;i<=lg[depth[now]];i++) fa[now][i]=fa[fa[now][i-1]][i-1];// 刚才的式子
- for(rg int i=head[now];i;i=nxt[i]){
- if(edge[i]!=pre) dfs(edge[i],now);// 遍历所有连接子节点 (非父亲节点) 的边, 递归下一层
- }
- }
求解 \(LCA\)
讲解都在代码注释里了, 直接贴代码吧
- inline int lca(int x,int y){
- if(depth[x]<depth[y]) swap(x,y);// 首先保证 x 的深度要大于 y, 便于操作
- while(depth[x]>depth[y]) x=fa[x][lg[depth[x]-depth[y]]-1];// 将 x 调到和 y 同层, 便于同时向上跳, 这里也用到了倍增
- if(x==y) return x;// 如果 x 恰好与 y 相同, 则证明 x 与 y 的 LCA 就是 x
- for(rg int k=lg[depth[x]]-1;k>=0;--k)// 向上跳
- if(fa[x][k]!=fa[y][k])
- x=fa[x][k],y=fa[y][k];
- return fa[x][0];// 跳到最后的 x 节点的父亲节点就是 LCA, 返回
- }
完整代码
- #include<iostream>
- #include<cstdio>
- #include<cstdlib>
- #include<cstring>
- #include<cctype>
- #include<cmath>
- using namespace std;
- #define rg register
- #define ll long long
- #define ull unsigned long long
- namespace Enterprise{
- inline int read(){
- rg int s=0,f=0;
- rg char ch=getchar();
- while(not isdigit(ch)) f|=(ch=='-'),ch=getchar();
- while(isdigit(ch)) s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
- return f?-s:s;
- }
- const int N=5e5+15;
- int head[N],edge[N<<1],nxt[N<<1],tot;
- int depth[N],fa[N][25],lg[N],n,m,s;
- inline void add(int u,int v){
- edge[++tot]=v;
- nxt[tot]=head[u];
- head[u]=tot;
- }
- inline void dfs(int now,int pre){
- fa[now][0]=pre;
- depth[now]=depth[pre]+1;
- for(rg int i=1;i<=lg[depth[now]];++i) fa[now][i]=fa[fa[now][i-1]][i-1];
- for(rg int i=head[now];i;i=nxt[i]){
- if(edge[i]!=pre) dfs(edge[i],now);
- }
- }
- inline int lca(int x,int y){
- if(depth[x]<depth[y]) swap(x,y);
- while(depth[x]>depth[y]) x=fa[x][lg[depth[x]-depth[y]]-1];
- if(x==y) return x;
- for(rg int k=lg[depth[x]]-1;k>=0;--k)
- if(fa[x][k]!=fa[y][k])
- x=fa[x][k],y=fa[y][k];
- return fa[x][0];
- }
- inline void main(){
- n=read(),m=read(),s=read();
- for(rg int i=1;i<n;i++){
- int u=read(),v=read();
- add(u,v);
- add(v,u);
- }
- for(rg int i=1;i<=n;i++) lg[i]=lg[i-1]+(1<<lg[i-1]==i);
- dfs(s,0);
- for(rg int i=1;i<=m;i++){
- int x=read(),y=read();
- printf("%d\n",lca(x,y));
- }
- }
- }
- signed main(){
- Enterprise::main();
- return 0;
- }
\(3.\)后记
关于代码中如下一段, 做一下说明
for(rg int i=1;i<=n;i++) lg[i]=lg[i-1]+(1<<lg[i-1]==i);
这是对于求解 \(log_2n\)的优化, 可以手推一下, 手推不出直接背过也可.
[算法学习笔记] 倍增求最近公共祖先(LCA, 非战斗机)
来源: http://www.bubuko.com/infodetail-3350222.html