当前位置：首页 > GESP > 2023年【GESP六级真题解析】工作沟通题目（LCA算法+Tarjan模板）：代码详解与优化思路

2023年【GESP六级真题解析】工作沟通题目（LCA算法+Tarjan模板）：代码详解与优化思路

6个月前 (09-02)

一、题目解读

2023年GESP六级“工作沟通”题目（洛谷P10109）要求处理公司层级关系，通过给定员工与直属领导的映射，实现多组查询：找出多个员工节点的共同上级（即最近公共祖先，LCA）。题目重点考察树结构处理、LCA算法设计与优化，需平衡时间与空间复杂度。

二、解题思路

采用离线处理+Tarjan算法框架，核心为：

1. 预处理阶段：构建树结构，存储每个节点的父节点及深度；利用倍增法预处理2^k级祖先，降低LCA查询复杂度。

2. 深度优先搜索（DFS）：计算节点深度并构建父子关系树。

3. LCA查询优化：通过深度调整与倍增跳跃，快速定位最近公共祖先。

4. Tarjan算法：离线处理多组查询，避免重复计算，提升效率。

三、解题步骤

1. 输入与初始化：读取N个节点及父子关系，构建树结构。

2. 预处理：

初始化父节点数组：parent[i]存储i的直属领导。

倍增预处理：计算up[i][k]（i的2^k级祖先）。

深度优先搜索：递归计算每个节点深度。

3. 查询处理：

对每组m个员工，通过LCA算法找到共同上级：

深度对齐：将深度较深的节点提升到与最浅节点同一层。

倍增跳跃：同步向上查找，直至找到最近公共祖先。

4. 输出结果：返回每组查询的LCA节点编号。

四、代码与注释

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

const int MAXN = 1e5 + 5;
const int LOG = 20;

vector<int> parent(MAXN);
vector<vector<int>> up(MAXN, vector<int>(LOG));
vector<int> depth(MAXN);

// 预处理每个节点的2^k级祖先
void preprocess(int n) {
    up[0][0] = 0; // 老板的父节点是自己
    for(int i = 1; i < n; ++i) {
        up[i][0] = parent[i];
    }
    
    for(int k = 1; k < LOG; ++k) {
        for(int i = 0; i < n; ++i) {
            up[i][k] = up[up[i][k-1]][k-1];
        }
    }
}

// 计算节点u的深度
void dfs(int u, int p, const vector<vector<int>>& children) {
    for(int v : children[u]) {
        if(v != p) {
            depth[v] = depth[u] + 1;
            dfs(v, u, children);
        }
    }
}

// 提升节点u到指定深度
int lift(int u, int target_depth) {
    for(int k = LOG-1; k >= 0; --k) {
        if(depth[u] - (1 << k) >= target_depth) {
            u = up[u][k];
        }
    }
    return u;
}

// 查找两个节点的LCA
int lca(int u, int v) {
    if(depth[u] < depth[v]) swap(u, v);
    u = lift(u, depth[v]);
    
    if(u == v) return u;
    
    for(int k = LOG-1; k >= 0; --k) {
        if(up[u][k] != up[v][k]) {
            u = up[u][k];
            v = up[v][k];
        }
    }
    return parent[u];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    cin >> N;
    
    vector<vector<int>> children(N);
    parent[0] = 0;
    for(int i = 1; i < N; ++i) {
        cin >> parent[i];
        children[parent[i]].push_back(i);
    }
    
    // 预处理
    preprocess(N);
    depth[0] = 0;
    dfs(0, -1, children);
    
    int Q;
    cin >> Q;
    while(Q--) {
        int m;
        cin >> m;
        vector<int> group(m);
        for(int i = 0; i < m; ++i) {
            cin >> group[i];
        }
        
        // 找到所有节点的LCA
        int current_lca = group[0];
        for(int i = 1; i < m; ++i) {
            current_lca = lca(current_lca, group[i]);
            if(current_lca == 0) break; // 已经到根节点
        }
        
        cout << current_lca << '\n';
    }
    
    return 0;
}