[学习笔记]lca-倍增

The article is to Jimmy.(方老师讲过了还不会,想怎样???)

The airticle is to Seakway.(我真的打过代码并且讲过了！！！)

求一棵树上两个节点的最近公共祖先有两种算法:

$1.tarjan$ (离线);

$2.$ 倍增(在线).

这篇博客只介绍倍增的写法.

$f[i][j]$ 表示节点 $i$ 的祖先中,与节点 $i$ 距离为 $2^j$ 的节点编号.

那么 $f[i][j]=egin{cases}root&i=root\father[i]&j=0,i ot=root\ f[i][j]=f[f[i][j-1]][j-1]&j>0,i ot=rootend{cases}$

每次查询两个节点 $x,y$ 的 $lca$ 时,现将深度深的点向上移,直到两个点的深度一样.

接下来就重复此工作,直到存在 $f[x][0]=f[y][0]$ :

找到最小的 $i$ 使得 $f[x][i]=f[y][i]$ ,如果 $i>0$ ,则令 $x=f[x][i-1],y=f[y][i-1]$ .

(这样的话能保证找到 $lca$ ,因为 $f[x][i]$ 为公共祖先, $f[x][i-1]$ 不是公共祖先,那么 $lca$ 会在 $father[f[x][i-1]]$ 到 $father[f[y][i-1]]$ 的路径上,所以需要退一级寻找.)

#include<cmath>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector> 
#include<string>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define K 20
#define N 10005
#define M 100005
using namespace std;
struct graph{
    int nxt,to;
}e[M];
int f[N][K],g[N],dep[N],m,n,q,cnt;
stack<int> s;
inline void addedge(int x,int y){
    e[++cnt].nxt=g[x];g[x]=cnt;e[cnt].to=y;
}
inline void dfs(int u){
    dep[u]=1;s.push(u);
    while(!s.empty()){
        u=s.top();s.pop();
        if(u!=1) for(int i=1;i<K;++i)
                f[u][i]=f[f[u][i-1]][i-1];
        else for(int i=0;i<K;++i)
            f[u][i]=u;
        for(int i=g[u];i;i=e[i].nxt){
            if(!dep[e[i].to]){
                dep[e[i].to]=dep[u]+1;
                f[e[i].to][0]=u;
                s.push(e[i].to);
            }
        }
    }
}
inline int swim(int x,int h){
    for(int i=0;h;++i,h>>=1)
        if(h&1) x=f[x][i];
    return x;
}
inline int lca(int x,int y){
    int i,t;
    if(dep[x]<dep[y]){
        t=x;x=y;y=t;
    }
    x=swim(x,dep[x]-dep[y]);
    if(x==y) return x;
    while(true){
        for(i=0;f[x][i]!=f[y][i];++i);
        if(!i) return f[x][0];
        x=f[x][i-1];y=f[y][i-1];
    }
}
inline void init(){
    scanf("%d%d",&n,&m);
    for(int i=1,j,k;i<=m;++i){
        scanf("%d%d",&j,&k);
        addedge(j,k);addedge(k,j);
    }
    scanf("%d",&q);dfs(1);
    for(int i=1,j,k;i<=q;i++){
        scanf("%d%d",&j,&k);
        printf("%d
",lca(j,k));
    }
}
int main(){
    freopen("lca.in","r",stdin);
    freopen("lca.out","w",stdout);
    init();
    fclose(stdin);
    fclose(stdout);
    return 0;
}