最近公共祖先就字面意思，两个节点一起往上跳，找到的最近的公共点
找到u和v第一个不同祖先不同的位置，然后这个位置向上走一步就是最近公共的祖先
但是想找到u,v第一个不同祖先的位置，就要保证u,v在同一深度（才能一起往上移动）
所以这个过程分为三部分，
1. 预处理找到每个节点深度
2. 把较深的一点移动到较浅一点的高度
3. 两个一起往上移动直到他们的父亲相同
预处理找深度
这里找深度可以用一个$deep$数组存下，用$bfs$找到所有深度，顺便可以把父节点也记录了
void bfs( int s ){ queue <int> fat,step;//队列存父节点以及深度 fa[s] = s;deep[s] = 1;//根节点的父亲还是自己，深度为1 fat.push(s);step.push(1);//放入根节点 int nf,ns;//队头的父节点以及深度 vis[s] = 1;//根节点已经遍历 while( !fat.empty() ){ nf = fat.front(); ns = step.front(); //取队头 fat.pop();step.pop(); for( int i = head[nf];i;i = e[i].next ){ //所有能到的边都算上（因为不知道边连接的两个点谁是父节点） int to = e[i].to; if( vis[to] ) continue; //如果目的点已经去过，con掉 fa[to] = nf; deep[to] = ns+1; //记录对应的数值 vis[to] = 1; st(to); //对该点初始化，一会再说 fat.push(to);step.push(deep[to]); } } }
找公共祖先
在两点跳到同样深度后，有两种做法
（一）一步一步暴力跳
（二）倍增
当然用倍增啦~
那我们就预处理一下$a[i][j]$，记录每个节点$i$往上跳$2^j$步后，跳到的祖先是谁
因为$i$移动$2^j$次就相当于从i移动$2^{j-1}$次后再移动$2^{j-1}$次 找到状态转移方程 $father [ i ] [ j ] = father [ father [ i ] [ j -1] ] [ j-1 ] ;$
然后用$dp$做一个预处理（在$bfs$时查到这个点就处理这个点）
void st( int p ){ a[p][0] = fa[p];//往上跳2^0=1步即找到自己的父节点 for( int i = 1;i <= 20;i++ ) //修改所有能跳的步数 a[p][i] = a[ a[p][i-1] ][i-1]; }
之后就开始跳就完了
int LCA( int x,int y ){ if( deep[x] < deep[y] ) swap( x,y ); //默认x更深 int h = deep[x] - deep[y];//取出高度差 for( int i = 0;i <= 20;i++ ) //保证每个都能测到 if( h & (1<<i) ) //二进制跳高度 x = a[x][i]; if( x == y ) return y; //如果y是x的祖先，返回y就行 for( int i = 20;i >= 0;i-- ){ //找到第一个不相同的节点 if( a[x][i] != a[y][i] ){ x = a[x][i]; y = a[y][i]; } } return a[x][0]; //公共祖先就是第一个不相同的点的上一个点 }
代码如下：
#include<iostream> #include<cstdio> #include<queue> #define NUM 500010 using namespace std; int n,m,s; int fa[NUM],deep[NUM]; int a[NUM][23]; struct bian{ int next,to; }; bian e[NUM<<1]; int head[NUM]; bool vis[NUM]; int cnt; void add( int x,int y ){ e[++cnt].next = head[x]; e[cnt].to = y; head[x] = cnt; } void st( int p ){ a[p][0] = fa[p]; for( int i = 1;i <= 20;i++ ) a[p][i] = a[ a[p][i-1] ][i-1]; } void bfs( int s ){ queue <int> fat,step; fa[s] = s;deep[s] = 1; for( int i = 0;i <= 20;i++ ) a[s][i] = s; fat.push(s);step.push(1); int nf,ns; vis[s] = 1; while( !fat.empty() ){ nf = fat.front(); ns = step.front(); fat.pop();step.pop(); for( int i = head[nf];i;i = e[i].next ){ int to = e[i].to; if( vis[to] ) continue; fa[to] = nf; deep[to] = ns+1; vis[to] = 1; st(to); fat.push(to);step.push(deep[to]); } } } int LCA( int x,int y ){ if( deep[x] < deep[y] ) swap( x,y ); int h = deep[x] - deep[y]; for( int i = 0;i <= 20;i++ )
if( h & (1<<i) ) x = a[x][i];
if( x == y ) return x; for( int i = 20;i >= 0;i-- ){ if( a[x][i] != a[y][i] ){ x = a[x][i]; y = a[y][i]; } } return a[x][0]; } int main(){ cin >> n >> m >> s; int x,y; for( int i = 1;i <= n-1;i++ ){ cin >> x >> y; add( x,y ); add( y,x ); } bfs( s ); // for( int i = 1;i <= n;i++ ) // for( int i = 1;i <= n;i++ ){ // printf( "\n节点i = %d，父亲为%d,深度为%d\n",i,fa[i],deep[i] ); // for( int j = 0;j <= 20;j++ ) // printf( " 往上%d下，为%d\n",j,a[i][j] ); // } for( int i = 1;i <= m;i++ ){ cin >> x >> y; int p = LCA(x,y); // if( p == 0 || p == -1 ) cout << s << endl; // else cout << p << endl;; } return 0; }
Warning:加黄部分要注意，确实要这么写
如果写成如下形式则WA
int cnt = 0; while( h&1 ){ x = a[x][cnt]; cnt++; h >>= 1; }
因为如果$h$的二进制为$11010$，则$while$会退出循环