G8002 [GESP202312 八级] 大量的工作沟通 题解

知识点：最近公共祖先、倍增、树上路径。

解题思路

预处理深度、倍增祖先，以及根到每点路径上的最大编号mx。查询时把参与者依次求LCA，再输出mx[LCA]。

为什么正确

所有参与者共同管理者是根到其共同祖先LCA的一整条链，题目要求编号最大，故需取链上最大编号而不是LCA编号本身。

易错点

父节点编号不保证小于孩子；六级小规模的逐点祖先表不适合本题大数据。

复杂度

预处理O(n log n)，单次查询O(m log n)，空间O(n log n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<vector<int>>g(n);
    vector<int>p(n),dep(n),mx(n);
    for(int i=1;i<n;i++) {
        cin>>p[i];
        g[p[i]].push_back(i);
    }
    vector<int>q= {
        0
    }
    ;
    for(int k=0;k<(int)q.size();k++)for(int v:g[q[k]]) {
        dep[v]=dep[q[k]]+1;
        mx[v]=max(mx[q[k]],v);
        q.push_back(v);
    }
    vector<vector<int>>up(18,p);
    for(int k=1;k<18;k++)for(int i=0;i<n;i++)up[k][i]=up[k-1][up[k-1][i]];
    auto lca=[&](int u,int v) {
        if(dep[u]<dep[v])swap(u,v);
        int dif=dep[u]-dep[v];
        for(int k=0;k<18;k++)if(dif>>k&1)u=up[k][u];
        if(u==v)return u;
        for(int k=17;k>=0;k--)if(up[k][u]!=up[k][v]) {
            u=up[k][u];
            v=up[k][v];
        }
        return p[u];
    }
    ;
    int Q;
    cin>>Q;
    while(Q--) {
        int m,x;
        cin>>m>>x;
        while(--m) {
            int y;
            cin>>y;
            x=lca(x,y);
        }
        cout<<mx[x]<<"\n";
    }
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用16个自行生成的测试点。