一. 知识引入
LCA即最近公共祖先，即有根树中x,y的公共祖先中深度最大的一个节点。
求最近公共祖先的方法：暴力法，向上标记法，树上倍增法，Tarjan算法。
【“暴力”法】
先 dfs求出对应点的 dep（深度），深度大的向上跳到与深度小的同一深度，
比较是否相同，不相同的话，两者一起往上跳。
【向上标记法】O(N)
从x点向上走到根节点，标记所有经过的节点。
从y点向上走到根节点的过程中，第一次遇到的已经标记的节点就是lca。
【树上倍增法】O(logN) （在线）
设f[i][k]表示点i往上的第2^k个祖先。
首先我们用复杂度O(N*lgN)的dfs预处理出f数组, 递推式：f[i][k]=f[f[i][k-1]][k-1]。
意义为：【i的2^(k-1)辈祖先】的2^(k-1)辈祖先 == i的2^k辈祖先。
1.首先，将两个点跳到同一深度（用二进制拆分思想）。
二进制拆分：依次尝试从x向上走k=2^logn,...,2^1,2^0步，检查到达的结点是否比y深。
每次若检查成功，则令x=f[x,k]，继续向上跳，若x=y，则已经找到了lca。
2.x、y同时向上调整并保持深度一致。
依次尝试把x、y同时向上走k=2^logn,...,2^1,2^0步，每次尝试过程中，
若f[x][k]!=f[y][k]，则跳过去，令x=f[x,k]，y=f[y,k]。否则不跳。
3.因为最后一步是：找到某个位置i，为最后一次f[a][i]!=f[b][i]（再无法向上跳）。
所以，最终的答案为f[x][0]（f[y][0]一样）。【Tarjan算法】 （离线）
1.任选一个点为根节点，从根节点开始。
2.遍历该点u所有子节点v，并标记这些子节点v已被访问过。
3.若是v还有子节点，返回2，否则下一步。
4.合并v到u上。
5.寻找与当前点u有询问关系的点v。
6.若是v已经被访问过了，则可以确认u和v的最近公共祖先为v被合并到的父亲节点a。假设我们有一组数据 9个节点 8条边 联通情况如下：
1--2，1--3，2--4，2--5，3--6，5--7，5--8，7--9 即下图所示的树
设我们要查找最近公共祖先的点为9--8，4--6，7--5，5--3；
设 f [ i ] 数组为并查集的父亲节点数组，初始化 f [ i ] = i，
vis[ i ] 数组为是否访问过的数组，初始为0 。
下面开始模拟过程：
取1为根节点，往下搜索发现有两个儿子2和3；
先搜2，发现2有两个儿子4和5，先搜索4，发现4没有子节点，则寻找与其有关系的点；
发现6与4有关系，但是vis[6]=0，即6还没被搜过，所以不操作；
发现没有和4有询问关系的点了，返回此前一次搜索，更新vis[4]=1；
表示4已经被搜完，更新f[4]=2，继续搜5，发现5有两个儿子7和8;
先搜7，发现7有一个子节点9，搜索9，发现没有子节点，寻找与其有关系的点；
发现8和9有关系，但是vis[8]=0，即8没被搜到过，所以不操作；
发现没有和9有询问关系的点了，返回此前一次搜索，更新vis[9]=1；
表示9已经被搜完，更新f[9]=7，发现7没有没被搜过的子节点了，寻找与其有关系的点；
发现5和7有关系，但是vis[5]=0，所以不操作；
发现没有和7有关系的点了，返回此前一次搜索，更新vis[7]=1；
表示7已经被搜完，更新f[7]=5，继续搜8，发现8没有子节点，则寻找与其有关系的点；
发现9与8有关系，此时vis[9]=1，则他们的最近公共祖先为find(9)=5；
( find(9) 的顺序为 f[9]=7 --> f[7]=5 --> f[5]=5 return 5; )
发现没有与8有关系的点了，返回此前一次搜索，更新vis[8]=1；
表示8已经被搜完，更新f[8]=5，发现5没有没搜过的子节点了，寻找与其有关系的点；
发现7和5有关系，此时vis[7]=1，所以他们的最近公共祖先为find(7)=5；
( find(7) 的顺序为 f[7]=5 --> f[5]=5 return 5; )
又发现5和3有关系，但是vis[3]=0，所以不操作，此时5的子节点全部搜完了；
返回此前一次搜索，更新vis[5]=1，表示5已经被搜完，更新f[5]=2；
发现2没有未被搜完的子节点，寻找与其有关系的点；
又发现没有和2有关系的点，则此前一次搜索，更新vis[2]=1；
表示2已经被搜完，更新f[2]=1，继续搜3，发现3有一个子节点6；
搜索6，发现6没有子节点，则寻找与6有关系的点，发现4和6有关系；
此时vis[4]=1，所以它们的最近公共祖先为find(4)=1;
( find(4) 的顺序为 f[4]=2 --> f[2]=2 --> f[1]=1 return 1; )
发现没有与6有关系的点了，返回此前一次搜索，更新vis[6]=1，表示6已经被搜完了；
更新f[6]=3，发现3没有没被搜过的子节点了，则寻找与3有关系的点；
发现5和3有关系，此时vis[5]=1，则它们的最近公共祖先为find(5)=1；
( find(5) 的顺序为 f[5]=2 --> f[2]=1 --> f[1]=1 return 1; )
发现没有和3有关系的点了，返回此前一次搜索，更新vis[3]=1；
更新f[3]=1，发现1没有被搜过的子节点也没有有关系的点，此时可以退出整个dfs了。
二. 例题详解
【例题1】洛谷p3379 lca模板题
#include <cmath>
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
//例题 P3379【模板】最近公共祖先（LCA）
#define maxn 500500
struct Edge{
int from,to;
}edges[2*maxn]; //边要乘2，因为是无向图
int firstt[maxn],nextt[2*maxn];
int read(){ //读入优化
int re=0; char ch=getchar();
while(ch<'0' || ch>'9') ch=getchar();
while(ch>='0' && ch<='9'){
re=re*10+ch-'0'; ch=getchar();
}
return re;
}
int n,m,root;
int height[maxn];
float log2n; //用于二进制拆分思想：向上走k=2^logn,...,2^1,2^0步
int f[maxn][20]; //f[i][k]即点i往上的第2^k个祖先，则f[i][0]是父亲
int have[maxn]; //have[i]记录有没有找过
void dfs(int u,int h){ //【预处理】深度+f数组
int v; height[u]=h; //u代表点的标号，h代表深度
for(int i=1;i<=log2n;i++){ //不超过logn层
if(h<=(1<<i)) break; //i是从小到大计算的,（1<<i>=h时可直接退出
f[u][i]=f[f[u][i-1]][i-1]; //状态转移
}
int k=firstt[u];
while(k!=-1){
v=edges[k].to;
if(!have[v]) have[v]=1, f[v][0]=u, dfs(v,h+1);
//↑↑↑将要找的下一个点的父节点标为当前处理的节点u
k=nextt[k];
}
}
int require_LCA(int a,int b){
int da=height[a],db=height[b];
if(da!=db){ //【第一步】将a，b两点移到同样的深度
if(da<db) swap(a,b),swap(da,db); //保证a的深度大于b
int d=da-db;
for(int i=0;i<=log2n;i++)
if( (1<<i) & d) a=f[a][i]; //【位运算】
//考虑到d是一个定值，而（1<<i）在二进制中只有第（i+1）位是1
//那么d &（1<<i）得到的答案，如果某一位为1，那么表示可以向上移动
//如果此时不移动，那么i增大了后就无法使height[a]==height[b]了
}
//【第二步】找到某个位置i，在这个位置时最后一次f[a][i]!=f[b][i]。
//从log2n开始从大到小枚举i，如果超过了a，b的高度，则令i继续减小。
//如果没有超过a，b的高度，那么就判断移动了后会不会让a==b。
//若a==b，则i继续减小; 否则，令此时的a=f[a][i],b=f[b][i]。
if(a==b) return b;
for(int i=log2n;i>=0;i--) {
if(height[f[a][i]]<0) continue;
if(f[a][i]==f[b][i]) continue;
else a=f[a][i],b=f[b][i];
}
return f[a][0];
}
int main(){
n=read(); m=read(); root=read();
memset(firstt,-1,sizeof(firstt));
memset(nextt,-1,sizeof(nextt));
int s,t,dsd=2*(n-1); //dsd用于编号
for(int i=1;i<=dsd;i+=2) {
s=read();t=read();
edges[i].from=s; edges[i].to=t; //无向图双向建边
edges[i+1].from=t; edges[i+1].to=s;
nextt[i]=firstt[s]; firstt[s]=i; //链式前向星
nextt[i+1]=firstt[t]; firstt[t]=i+1;
}
log2n=log(n)/log(2)+1; //求log2n，对无理数加上1或0.5可以减小误差
memset(have,0,sizeof(have));
memset(height,0,sizeof(height));
memset(f,-1,sizeof(f));
have[root]=1; dfs(root,1); //have[]记得初始化
for(int i=1;i<=n;i++)
for(int j=0;j<=log2n;j++)
if(height[i] <=(1<<j) ) break;
for(int i=0;i<m;i++){
s=read();t=read();
int y=require_LCA(s,t);
printf("%d\n",y);
}
return 0;
}
【例题2】hdoj 2586 任意两点间距离
#include <cmath>
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
/*【倍增求lca】hdoj 2586
给你一个N个点的树和Q次查询，每次查询问你任意两点间距离。*/
//<u,v>距离=dist[u]+dist[v]-2*dist[LCA(u,v)]。其中dist存储节点到根的距离。
const int maxn=100005;
int n,q,x,y,z,now;
int nextt[maxn*2],firstt[maxn*2],go[maxn*2]; //边的连向关系
int dep[maxn],dist[maxn],edge[maxn];
int f[maxn][21]; //f[i][k]即点i往上的第2^k个祖先
int adds(int u,int v,int z){ //前向星建边,z为价值
nextt[++now]=firstt[u]; firstt[u]=now;
edge[now]=z; go[now]=v;
nextt[++now]=firstt[v]; firstt[v]=now;
edge[now]=z; go[now]=u;
}
void pre_dfs(int u,int fa){ //预处理
for(int i=0;i<=19;i++) f[u][i+1]=f[f[u][i]][i];
for(int e=firstt[u];e;e=nextt[e]){
int v=go[e]; //找到下一条相连的边
if(v==fa) continue;
dep[v]=dep[u]+1; //深度
dist[v]=dist[u]+edge[e]; //距离
f[v][0]=u; pre_dfs(v,u); //记录father，递归
}
}
int lca(int x,int y){ //找lca的主程序
if(dep[x]<dep[y]) swap(x,y); //保证dep[x]>dep[y]
for(int i=20;i>=0;i--){ //注意：这里的20和上面的19都是log2n的近似取值
if(dep[f[x][i]]>=dep[y]) x=f[x][i];
//↑↑↑i的2^k辈祖先的结点仍比y深，令x=f[x,i]，继续向上跳
if(x==y) return x; //若x=y，则已经找到了lca
}
for(int i=20;i>=0;i--) //↓↓↓未找到lca时的倍增跳法
if(f[x][i]!=f[y][i]){ x=f[x][i]; y=f[y][i]; }
return f[x][0]; //最终的答案为f[x][0]
}
int main(){
int T; scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++) firstt[i]=nextt[i]=dep[i]=0;
now=0; dep[1]=1; //↓↓↓读入带权树
for(int i=1;i<n;i++){ scanf("%d%d%d",&x,&y,&z); adds(x,y,z); }
pre_dfs(1,0); //从根节点fa=0开始dfs预处理
while(q--){
scanf("%d%d",&x,&y);
printf("%d\n",dist[x]+dist[y]-2*dist[lca(x,y)]);
}
}
return 0;
}↓↓↓ tarjan算法代码
#include <cmath>
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=50010;
struct node{ int next,to,w; }edge[N]; //树的链表
int x,y,z,num_edge,head[N];
int fa[N],vis[N],dis[N],lca[N],ans[N];//vis[i]判断是否被找过
vector<int> query[N],query_id[N];
void add_edge(int from,int to,int dist){ //建边：链式前向星
edge[++num_edge].next=head[from];
edge[num_edge].to=to; head[from]=num_edge;
edge[num_edge].w=dist;
}
void add_qedge(int x,int y,int id){
query[x].push_back(y), query_id[x].push_back(id);
query[y].push_back(x), query_id[y].push_back(id);
}
int find(int x){ //并查集找祖先（题目理解中的find函数）
if(fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
void tarjan(int x){ //把整棵树的一部分看作以节点x为根节点的小树
vis[x]=1; //标记为已被搜索过
for(int k=head[x];k;k=edge[k].next){ //遍历所有与x相连的节点
int y=edge[k].to;
if(vis[y]) continue;
dis[y]=dis[x]+edge[k].w;
tarjan(y); fa[y]=x;
}
for(int i=0;i<query[x].size();i++){
int y=query[x][i], id=query_id[x][i];
if(vis[y]==2){
int lca=find(y);
ans[id]=min(ans[id],dis[x]+dis[y]-2*dis[lca]);
}
}
vis[x]=2;
}
int main(){
int T,n,m; cin>>T;
while(T--){
cin>>n>>m;
for(int i=1;i<=n;i++){
head[i]=0; vis[i]=0; fa[i]=i;
query[i].clear();
query_id[i].clear();
}
num_edge=0; //↑↑初始化清零
for(int i=1;i<n;++i){ //注意：只到n-1
scanf("%d%d%d",&x,&y,&z); //输入每条边
add_edge(x,y,z); add_edge(y,x,z);
}
for(int i=1;i<=m;++i){
scanf("%d%d",&x,&y);
if(x==y) ans[i]=0;
else{ add_qedge(x,y,i); ans[i]=1<<30; }
}
tarjan(1);
for(int i=1;i<=m;i++) //离线输出答案
printf("%d\n",ans[i]);
}
return 0;
}
——时间划过风的轨迹，那个少年，还在等你。