G6004 [GESP202312 六级] 工作沟通 题解

知识点：树、祖先关系、集合交集。

解题思路

预处理每名员工包含自己的全部祖先标记。每次查询从最大编号向下找，首个属于所有参与者祖先集合的人就是答案。

为什么正确

一个人能管理全部参与者，当且仅当在每人的祖先集合内；倒序枚举得到合法候选中编号最大者。

易错点

题目取编号最大，并非无条件取深度最深；本人也是自己的管理者，老板编号为0。

复杂度

预处理O(n²)，每次查询O(nm)，空间O(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<int>p(n);
    for(int i=1;i<n;i++)cin>>p[i];
    vector<vector<int>>anc(n,vector<int>(n));
    for(int i=0;i<n;i++) {
        int x=i;
        while(true) {
            anc[i][x]=1;
            if(x==0)break;
            x=p[x];
        }
    }
    int q;
    cin>>q;
    while(q--) {
        int m;
        cin>>m;
        vector<int>a(m);
        for(int &x:a)cin>>x;
        for(int x=n-1;x>=0;x--) {
            bool ok=true;
            for(int y:a)ok&=anc[y][x];
            if(ok) {
                cout<<x<<"\n";
                break;
            }
        }
    }
}

说明

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