? 优质资源分享 ?

最近公共祖先就字面意思，两个节点一起往上跳，找到的最近的公共点

找到u和v第一个不同祖先不同的位置，然后这个位置向上走一步就是最近公共的祖先

但是想找到u,v第一个不同祖先的位置，就要保证u,v在同一深度（才能一起往上移动）

所以这个过程分为三部分，

　　1. 预处理找到每个节点深度

　　2. 把较深的一点移动到较浅一点的高度

　　3. 两个一起往上移动直到他们的父亲相同

预处理找深度

这里找深度可以用一个deepdeepdeep数组存下，用bfsbfsbfs找到所有深度，顺便可以把父节点也记录了

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]);
 }
 }
}

BFS找深度与父节点
 

找公共祖先

在两点跳到同样深度后，有两种做法

　　（一）一步一步暴力跳

　　（二）倍增

当然用倍增啦~

那我们就预处理一下a[i][j]a[i][j]a[i][j]，记录每个节点iii往上跳2j2j2^j步后，跳到的祖先是谁

因为iii移动2j2j2^j次就相当于从i移动2j−12j−12^{j-1}次后再移动2j−12j−12^{j-1}次 找到状态转移方程 $father [ i ] [ j ] = father [ father [ i ] [ j -1] ] [ j-1 ] ;$

然后用dpdpdp做一个预处理（在bfsbfsbfs时查到这个点就处理这个点）

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<//二进制跳高度 
 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
#include
#include
#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;
}

因为如果hhh的二进制为110101101011010，则whilewhilewhile会退出循环

转载请注明：xuhss » LCA最近公共祖先