树上倍增求 LCA
以 P3379 为模板来讲解。
-
对于每个结点
\text{dfs} 预处理出结点深度。 -
求
\text{st} 表，st_{i,j} 表示结点i 往上跳2^j 步到达的结点。-
初始值：
st_{i,0}=fa_i 。2^0=1 ，i 往上跳一步就是i 的父亲结点 -
递推式：
st[i][j]=st[st[i][j-1]][j-1]。结点i 跳2^j 步到达的结点就是i 跳2^{j-1} 步后再跳2^{j-1} 步到达的结点。
-
对于查询
-
如果
x 的深度小于y 的深度，则交换x 和y ，使得x 更深。 -
采用二进制拆分的思想，让
x 跳得跟y 一样高。 -
如果此时
x=y ，直接返回x 。 -
否则让
x 和y 倍增往上跳，跳到它们\text{LCA} 的两个子结点，最后再跳一步即可得出x 和y 的\text{LCA} 。
#include<iostream>
#include<cstdio>
using namespace std;
const int N=5e5+100,LG=30;
int n,m,t[N],k,deep[N],st[N][LG],x,y,lg[N],s;
struct node
{
int id,last;
}a[N*2];
void add(int a1,int a2)//建边
{
a[++k].id=a2;
a[k].last=t[a1];
t[a1]=k;
}
void dfs(int dx,int fa)//预处理出每个结点的深度
{
deep[dx]=deep[fa]+1;//当前结点深度为父亲结点深度+1
st[dx][0]=fa;//st表初始值
for(int i=t[dx];i;i=a[i].last)//递归子结点
{
if(a[i].id!=fa) dfs(a[i].id,dx);
}
}
int lca(int dx,int dy)//求x和y的LCA
{
if(deep[dx]<deep[dy]) swap(dx,dy);//使得x的深度更深
for(int i=lg[n];i>=0;i--)//让x跳得跟y一样高
{
if(deep[st[dx][i]]>=deep[dy]) dx=st[dx][i];
if(dx==dy) return dx;//x和y重合，LCA为x
}
for(int i=lg[n];i>=0;i--)//x和y倍增往上跳，跳到LCA的两个子结点
{
if(st[dx][i]!=st[dy][i]) dx=st[dx][i],dy=st[dy][i];
}
return st[dx][0];//再跳一步得到LCA
}
int main()
{
scanf("%d%d%d",&n,&m,&s);
for(int i=2;i<=n;i++) lg[i]=lg[i/2]+1;
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
//双向建边，因为不知道父子关系
add(x,y);
add(y,x);
}
dfs(s,0);
for(int i=1;i<=lg[n];i++)//求st表
{
for(int j=1;j<=n;j++) st[j][i]=st[st[j][i-1]][i-1];
}
while(m--)
{
scanf("%d%d",&x,&y);
printf("%d\n",lca(x,y));
}
return 0;
}