倍增算法

1.求LCA

首先求出每个节点的深度, 如果我们要求u, v 的LCA

首先找到 u 的一个和 v 在同一深度的祖先 u’ , 则 LCA(u, v) = LCA(u’ , v)

若 u’ = v , 说明 u’ 正好就是LCA(u, v) , 否则:

• u’, v 两个点同时向上跳 2^j 步,
  1. 若指向同一个点, 说明他们距离LCA小于等于 2^j , 此时我们减少上跳幅度
  2. 若指向不同的点, 重复 1, 2, 直到 j = 0, 再跳一步, 正好到达 LCA

算法步骤

1. dfs预处理, f[i][j] 表示 i 的 2^j 级祖先

void dfs(int u,int fa){
    dep[u]=dep[fa]+1;//当前节点深度为父节点深度 +1
    for(int i=1;(1<<i)<=dep[u];i++)
        f[u][i]=f[f[u][i-1]][i-1];//根据u的深度，预处理其2^i祖先 
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(v==fa)continue;
        f[v][0]=u;//v的父亲节点是u 
        dfs(v,u);
    }
}

2.上调至同一深度

当u, v不在同一个深度时，我们要用倍增思想把深度大的节点u调到和v在同一个深度。

int len=dep[u]-dep[v],k=0;
while(len){//对k进行二进制分解
    if(len & 1) u=f[u][k];//如果当前位为1
    ++k;len>>=1;//k记录处理到 len 的第几个二进制位

3. 代码全貌

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+5,maxe=1e5+5;
int n, len, head[maxn], dep[maxn], f[maxn][21];
struct edge{
    int next,to;
}e[2*maxe];
void Insert(int u,int v){
    e[++len].to=v;
    e[len].next=head[u];
    head[u]=len;    
}
void dfs(int u,int fa){
    dep[u] = dep[fa] + 1;
    for(int i=1; i<=dep[u]; i++) f[u][i] = f[f[u][i-1]][i-1];
    for(int i=head[u]; i; i=e[i].next){
        int v = e[i].to;
        if(v == fa) continue;
        dfs(v, u);
        f[v][0] = u;
    }
}
int lca(int u,int v){
    if(dep[u] < dep[v]) swap(u, v);
    int len = dep[u] - dep[v], k = 0;
    while(len){
        if(len & 1) u = f[u][k];
        k++; len >>= 1;
    }
    if(u == v) return u;
    for(int i=20; i>=0; i--){
        if(f[u][i] == f[v][i]) continue;
        u = f[u][i]; v = f[v][i];
    }
    return f[u][0];
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int x,y;scanf("%d%d",&x,&y);
        Insert(x,y);Insert(y,x);
    }
    dfs(1,0);
    int Q;scanf("%d",&Q);
    for(int i=1;i<=Q;i++){
        int u,v;scanf("%d%d",&u,&v);
        printf("%d\n",dep[u]+dep[v]-2*dep[lca(u,v)]);//求两个节点的LCA 
    }
}