题解：P3379 【模板】最近公共祖先（LCA）

· · 题解

题目描述

给定一棵包含n个节点的树，处理 m次查询，每次查询两个节点的最近公共祖先。

算法思路

‌1. 预处理‌：通过DFS初始化每个节点的深度和直接父节点。

2. 倍增

核心思想： 每个节点的2^j级祖先可以通过两次2^{j-1}级跳跃得到。

即：f[i][j]=节点i向上跳2^{j-1}步后的祖先，再向上跳 2^{j-1}步。

f[i][j]表示第i个节点向上跳2^j步所到达的节点位置。

可以易知f[i][0]是节点i的父亲节点。

由此可得出递推式：

f[i][j]=f[f[i][j-1]][j-1]

代码如下：

for(int j=1;(1<<j)<=n;j++){
    for(int i=1;i<=n;i++){
        f[i][j]=f[f[i][j-1]][j-1];
    }
}

分析：

循环逻辑‌

A. 外层循环j：

‌作用‌：枚举跳跃步长的指数j，即2^j步。 ‌终止条件‌：2^j\leq n。

因为树的高度最多为n，超过 2^j>n的跳跃无意义。

B. 内层循环i‌：

‌作用‌：对每个节点i，计算其2^j级祖先。

3. 查询LCA‌：将两个节点调整到同一深度，然后同时向上跳跃，找到最近的公共祖先。

代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+7;
int n,m,s,f[N][30],dep[N];
bool vis[N];
vector<int> g[N];
void dfs(int u,int fa){
    f[u][0]=fa;//f[u][0]表示第u个节点的父亲节点
    dep[u]=dep[fa]+1;//每个节点的深度是其父亲节点的深度+1
    for(auto v:g[u]){
        if(v==fa)continue;//防止遍历回父亲节点
        dfs(v,u);
    }
}
int lca(int u,int v){
    if(dep[u]<dep[v])swap(u,v);//令u始终在v的下方
    for(int i=22;i>=0;i--){
        if(dep[f[u][i]]>=dep[v])u=f[u][i];
        //将u往上拉，直至dep[u]=dep[v] 
    }
    if(u==v)return u;//此时v为u的祖先，直接返回u
    //此时u与v已在同一深度上
    for(int i=22;i>=0;i--){
        if(f[u][i]!=f[v][i]){
            u=f[u][i];
            v=f[v][i];
            //将u和v一同向上拉，直至两点位于同一个节点上
        }
    }
    return f[u][0];//或f[v][0](u与v共同的父亲节点) 
}
void init(){
    //倍增初始化
    for(int j=1;(1<<j)<=n;j++){
        for(int i=1;i<=n;i++){
            f[i][j]=f[f[i][j-1]][j-1];
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>s;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
        //存入数据
    }
    dfs(s,0);
    init();
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        cout<<lca(u,v)<<"\n";
    }
    return 0;
}

蒟蒻第一次写题解，可能很垃