倍增求LCA模板

//dfs预处理出每个节点的深度和2的x方级祖先节点
void dfs(int now,int fa,int da){
//now为当前节点,fa为父亲节点,da为父亲节点和儿子节点所连边的边权
    cost[now][0]=da;
    zx[now][0]=fa;
    dep[now]=dep[fa]+1;
//cost[x][i]表示x节点到它的2的i次方级祖先节点的距离
//zx[x][i]表示x节点的2的i次方级祖先节点的编号
//dep[x]表示x节点的深度
    for(int i=1;(1<<i)<=dep[now];i++){
        zx[now][i]=zx[zx[now][i-1]][i-1];
//类似于你父亲的父亲是你的祖父
        cost[now][i]=cost[now][i-1]+cost[zx[now][i-1]][i-1];
    }
//处理出now的2的i次方级节点的编号和now到now的2的i次方级祖先节点的距离
    for(int i=head[now];i!=-1;i=b[i].next){
        if(fa!=b[i].to) dfs(b[i].to,now,b[i].val);
//递归处理
    }
}
int lca(int x,int y){
//查询x与y的LCA
    int ans=0;
    if(dep[x]>dep[y]) swap(x,y);
//使x的深度小于y的深度
    int len=dep[y]-dep[x],k=0;
    while(len){
    	if(len & 1){
            ans+=cost[y][k];
            y=zx[y][k];
        }
    	++k;len>>=1;
    }
//将y调到与x相同的深度，同时累加距离
    if(x==y) return ans;
//如果调到相同深度后两节点重合，直接返回权值就可以
    for(int i=20;i>=0;i--){
        if(zx[x][i]==zx[y][i]) continue;
        ans+=cost[x][i]+cost[y][i];
        x=zx[x][i];
        y=zx[y][i];
    }
//将x和y向上跳，直到它们的父亲节点相同
    return ans+cost[x][0]+cost[y][0];
//返回累加的权值与x，y到它们的父亲节点的权值
}

倍增求LCA模板

原文：https://www.cnblogs.com/liuchanglc/p/12816848.html