[学习笔记]lca-倍增

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

1. \(tarjan\)(离线);
2. 倍增(在线).

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

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

那么\(f[i][j]=\begin{cases}root&i=root\\ father[i]&j=0,i\not=root\\ f[i][j]=f[f[i][j-1]][j-1]&j>0,i\not=root\end{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
#include
#include
#include
#include 
#include
#include
#include
#include
#include
#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 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>=1)
        if(h&1) x=f[x][i];
    return x;
}
inline int lca(int x,int y){
    if(dep[x]