[GESP202312 六级] 工作沟通(Work Communication) 题解

思路分析

每位员工的合法管理者集合就是他在以 $0$ 为根的组织树上的所有祖先（含自身）。注意题目并未保证 $f_i < i$，因此所有参与者的最近公共祖先（最深公共领导）不一定编号最大！由于 $N \le 300$，对每次询问中的每名参与者不断沿 $f_u$ 向上跳到根 $0$，统计每个结点成为祖先的次数 cnt[x]；在所有满足 cnt[x] == m 的公共领导中取编号最大的 $x$ 输出即可。时间复杂度 $O(QN)$。

参考代码

#include <iostream>
using namespace std;

int fa[305];
int cnt[305];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    fa[0] = -1;
    for (int i = 1; i < n; ++i) cin >> fa[i];
    int q;
    cin >> q;
    while (q--)
    {
        for (int i = 0; i < n; ++i) cnt[i] = 0;
        int m;
        cin >> m;
        for (int i = 0; i < m; ++i)
        {
            int u;
            cin >> u;
            while (u != -1)
            {
                cnt[u]++;
                u = fa[u];
            }
        }
        int ans = 0;
        for (int x = n - 1; x >= 0; --x)
        {
            if (cnt[x] == m)
            {
                ans = x;
                break;
            }
        }
        cout << ans << "\n";
    }
    return 0;
}