posted on 2021-08-04 14:22:40 | under 学术 | source
LCA，Least Common Ancestors，最近公共祖先。
倍增。
首先预处理出数组 \(d_i\) 和 \(f_{i,j}\)。
- \(d_i\) 表示第 \(i\) 个节点的深度。
转移方程：\(d_{i}=d_{\text{fa}}+1\) - \(f_{i,j}\) 表示第 \(i\) 个节点的第 \(2^j\) 级祖先。
转移方程：\(f_{i,0}=\text{fa},f_{i,j}=f_{f_{i,j-1},j-1}\)
接着是 LCA。分成以下几个步骤：
- 把 \(x,y\) 跳到同一层。
- 使用倍增思想把 \(x,y\) 跳到离 LCA 最近的节点。
- 最终 \(f_{x,0}\) 或 \(f_{y,0}\) 为 \(x,y\) 的 LCA。
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
template<int N,int M> struct Graph{
int cnt,head[N+10];
struct Edge{
int s,e,w,nxt;
Edge(int s=0,int e=0,int w=0,int nxt=0):
s(s),e(e),w(w),nxt(nxt){}
} a[(M<<1)+10];
Graph():cnt(0){memset(head,0,sizeof head);}
void add(int s,int e,int w=0){a[++cnt]=Edge(s,e,w,head[s]),head[s]=cnt;}
void link(int s,int e,int w=0){add(s,e,w),add(e,s,w);}
};
template<int N> struct Math{
int lg[N+10];
Math(){
lg[0]=-1;
for(int i=1;i<=N;i++) lg[i]=lg[i>>1]+1;
}
int log(int x){return lg[x];}
int pow(int x){return 1<<x;}
};
int n,m;
Graph<500010,500010> g;
Math<5000010> math;
int f[500010][21],d[500010];
void dfs(int root,int fa){
f[root][0]=fa,d[root]=d[fa]+1;
for(int i=1;i<=math.log(d[root]);i++){
f[root][i]=f[f[root][i-1]][i-1];
}
for(int i=g.head[root];i;i=g.a[i].nxt){
int to=g.a[i].e;
if(to!=fa) dfs(to,root);
}
}
int lca(int x,int y){
if(d[x]<d[y]) swap(x,y);
int jmp=d[x]-d[y];
for(int i=math.log(jmp);i>=0;i--){
if((jmp>>i)&1) x=f[x][i];
}
if(x==y) return x;
for(int i=math.log(n);i>=0;i--){
if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
}
return f[x][0];
}
int root;
int main(){
cin>>n>>m>>root;
for(int i=1;i<=n-1;i++){int x,y;
cin>>x>>y;
g.link(x,y);
}
dfs(root,root);
for(int i=1;i<=m;i++){int x,y;
cin>>x>>y;
cout<<lca(x,y)<<endl;
}
return 0;
}