最近公共祖先LCA（学习笔记）
LCA
P3379 【模板】最近公共祖先（LCA）
定义：
在一棵树上，任意两个节点，往上找的最近的公共根节点就是他们两个的最近公共祖先
作用：
可用于求树上任意两个点的路径和其路径的权值关系，如边权最大值，边权和等，都是以
实现：
倍增：
倍增，顾名思义，运用了指数打表的思想。
1.我们要用
dfs 遍历每一点，预处理求出每一节点的i 次倍后的父亲节点，及f_{x,i} 表示点x 的2^i 个祖先，并且找到每一个节点的深度
void dfs(int u,int fa){
d[u]=d[fa]+1;
f[u][0]=fa;
for(int i=1;(1<<i)<=d[u];i++)f[u][i]=f[f[u][i-1]][i-1];
for(int i=0;i<e[u].size();i++){
int v=e[u][i];
if(v==fa)continue;
dfs(v,u);
}
}2.倍增求
LCA 时，我们先要确保要找的点在同一深度。让后一起向上跳求LCA 。因此先要判断两节点的深度，在将深的往上跳，直到跳到同一深度。这时要判断是否相等，预防一个节点就是另一节点的根节点。相等则直接返回3.等两节点在同一高度后，在同时向上跳，知道跳完，这是，两节点所在节点就是
LCA ，输出即可，若要求路径关系，在dfs 时顺便也预处理一下，数值，后面相同
int lca(int x,int y){
if(d[x]<d[y])swap(x,y);
for(int i=20;i>=0;i--){
if(d[f[x][i]]<d[y])continue;
x=f[x][i];
}
if(x==y)return x;
for(int i=20;i>=0;i--){
if(f[x][i]==f[y][i])continue;
x=f[x][i];
y=f[y][i];
}
return f[x][0];
}注意：
1.
2.要给根节点的父节点和根节点深度赋值
完整代码：
#include<bits/stdc++.h>
using namespace std;
const int N=6e5+10;
vector<int>e[N];
int f[N][32],d[N];
void dfs(int u,int fa){
d[u]=d[fa]+1;
f[u][0]=fa;
for(int i=1;(1<<i)<=d[u];i++)f[u][i]=f[f[u][i-1]][i-1];
for(int i=0;i<e[u].size();i++){
int v=e[u][i];
if(v==fa)continue;
dfs(v,u);
}
}
int lca(int x,int y){
if(d[x]<d[y])swap(x,y);
for(int i=20;i>=0;i--){
if(d[f[x][i]]<d[y])continue;
x=f[x][i];
}
if(x==y)return x;
for(int i=20;i>=0;i--){
if(f[x][i]==f[y][i])continue;
x=f[x][i];
y=f[y][i];
}
return f[x][0];
}
int main(){
int n,m,s;
cin>>n>>m>>s;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
d[s]=1;
dfs(s,0);
while(m--){
int u,v;
cin>>u>>v;
cout<<lca(u,v)<<endl;
}
}练习：