当前位置：首页 > GESP > 洛谷P10113题（2023年GESP八级）：用LCA算法高效解决大量的工作沟通

洛谷P10113题（2023年GESP八级）：用LCA算法高效解决大量的工作沟通

5天前

一、题目解读

洛谷P10113题（2023年GESP八级）要求解决树结构中多个节点的最近公共祖先（LCA）查询问题。给定一棵树及若干组节点，需快速找出每组节点的LCA。传统方法如暴力遍历时间复杂度较高，而本题采用倍增法（RMQ算法）优化，通过预处理实现O(logN)的查询效率，适用于大规模数据场景。

二、解题思路

核心是倍增法（基于ST表思想的变体），通过构建“倍增表”预处理每个节点的祖先信息。关键在于利用二进制拆分思想：

1. 预处理阶段：计算每个节点深度，构建up[i][j]表表示节点i的2^j层祖先。

2. 查询阶段：通过二分提升深度差异，再同步向上移动找到LCA。

此思路将单次查询复杂度降至O(logN)，大幅优化性能。

三、解题步骤

1. 预处理阶段

● 初始化根节点（0号节点）深度为0，父节点为自身。

● 递归计算子节点深度：depth[i] = depth[parent[i]] + 1。

● 填充倍增表：up[i][j] = up[up[i][j-1]][j-1]，即节点i的2^j祖先通过其2^(j-1)祖先的2^(j-1)祖先间接获得。

2. LCA查询

● 确保较深节点u与v深度对齐：通过二进制拆分快速提升u至与v同深度。

● 同步向上：从最高位开始，若u、v的2^j祖先不同，则同时向父节点移动。最终两者父节点即为LCA。

四、代码与注释

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 1e5 + 5;  
const int LOG = 20; // 足够大的对数级别  

vector<int> parent(MAXN); // 存储每个节点的直接领导  
vector<int> depth(MAXN);  // 存储每个节点的深度  
vector<vector<int>> up(MAXN, vector<int>(LOG)); // 倍增表  

// 预处理函数，构建倍增表  
void preprocess(int n) {  
    depth[0] = 0;  
    up[0][0] = 0; // 根节点的2^0祖先还是自己  
    for(int i = 1; i < n; ++i) {  
        depth[i] = depth[parent[i]] + 1;  
        up[i][0] = parent[i]; // 2^0祖先就是直接领导  
    }  
    for(int j = 1; j < LOG; ++j) {  
        for(int i = 0; i < n; ++i) {  
            up[i][j] = up[up[i][j-1]][j-1];  
        }  
    }  
}  

// 查找两个节点的LCA  
int lca(int u, int v) {  
    if(depth[u] < depth[v]) swap(u, v); // 确保u更深  
    for(int j = LOG-1; j >= 0; --j) {  
        if(depth[u] - (1 << j) >= depth[v]) {  
            u = up[u][j]; // 提升u  
        }  
    }  
    if(u == v) return u; // u和v已重合  
    for(int j = LOG-1; j >= 0; --j) {  
        if(up[u][j]!= up[v][j]) {  
            u = up[u][j];  
            v = up[v][j];  
        }  
    }  
    return parent[u]; // 最终LCA为u的父节点  
}  

int main() {  
    ios::sync_with_stdio(false);  
    cin.tie(nullptr);  
    int N; cin >> N;  
    // 读取每个员工的直接领导
    for(int i = 1; i < N; ++i) cin >> parent[i];  
    // 预处理倍增表
    preprocess(N);  
    int Q; cin >> Q;  
    while(Q--) {  
        int m; cin >> m;  
        vector<int> employees(m);  
        for(int i = 0; i < m; ++i) cin >> employees[i];  
         // 找出所有员工的LCA
        int current_lca = employees[0];  
        for(int i = 1; i < m; ++i) {  
            current_lca = lca(current_lca, employees[i]);  
        }  
        cout << current_lca << '\n';  
    }  
}

注释说明：

● up[i][j] 存储节点i的2^j层祖先，预处理通过迭代构建。

● lca(u, v) 函数通过二分法对齐深度，再同步向上查找LCA。