2023年12月GESP真题及题解(C++八级): 大量的工作沟通-编程阁

2023年12月GESP真题及题解(C++八级): 大量的工作沟通

题目描述

某公司有N NN名员工，编号从0 00至N − 1 N-1N−1。其中，除了0 00号员工是老板，其余每名员工都有一个直接领导。我们假设编号为i ii的员工的直接领导是f i f_ifi。

该公司有严格的管理制度，每位员工只能受到本人或直接领导或间接领导的管理。具体来说，规定员工x xx可以管理员工y yy，当且仅当x = y x=yx=y，或x = f y x=f_yx=fy，或x xx可以管理f y f_yfy。特别地，0 00号员工老板只能自我管理，无法由其他任何员工管理。

现在，有一些同事要开展合作，他们希望找到一位同事来主持这场合作，这位同事必须能够管理参与合作的所有同事。如果有多名满足这一条件的员工，他们希望找到编号最大的员工。你能帮帮他们吗？

输入格式

第一行一个整数N NN，表示员工的数量。

第二行N − 1 N-1N−1个用空格隔开的正整数，依次为f 1 , f 2 , … f N − 1 f_1, f_2, \dots f_{N-1}f1,f2,…fN−1。

第三行一个整数Q QQ，表示共有Q QQ场合作需要安排。

接下来Q QQ行，每行描述一场合作：开头是一个整数m mm（2 ≤ m ≤ N 2 \leq m \leq N2≤m≤N），表示参与本次合作的员工数量；接着是m mm个整数，依次表示参与本次合作的员工编号（保证编号合法且不重复）。

保证公司结构合法，即不存在任意一名员工，其本人是自己的直接或间接领导。

输出格式

输出Q QQ行，每行一个整数，依次为每场合作的主持人选。

输入输出样例 1

输入 1

5 0 0 2 2 3 2 3 4 3 2 3 4 2 1 4

输出 1

2 2 0

输入输出样例 2

输入 2

7 0 1 0 2 1 2 5 2 4 6 2 4 5 3 4 5 6 4 2 4 5 6 2 3 4

输出 2

2 1 1 1 0

说明/提示

样例解释 1

对于第一场合作，员工3 , 4 3,43,4有共同领导2 22，可以主持合作。

对于第二场合作，员工2 22本人即可以管理所有参与者。

对于第三场合作，只有0 00号老板才能管理所有员工。

数据范围

对于25 % 25\%25%的测试点，保证N ≤ 50 N \leq 50N≤50。

对于50 % 50\%50%的测试点，保证N ≤ 300 N \leq 300N≤300。

对于所有测试点，保证3 ≤ N ≤ 10 5 3 \leq N \leq 10^53≤N≤105，Q ≤ 100 Q \leq 100Q≤100，m ≤ 10 4 m \leq 10^4m≤104

思路分析

问题本质：给定一棵树（根为0），每个查询给出一个节点集合，需要找到这些节点的所有公共祖先中编号最大的一个。
关键转换：
- 节点 x 是节点 y 的祖先当且仅当 x 在从 y 到根的路径上。
- 因此，集合 S 的所有公共祖先就是 S 中所有节点到根路径的交集，这个交集恰好是从 S 的最近公共祖先（LCA）到根的路径上的所有节点。
- 问题转化为：先求 S 中所有节点的 LCA，然后求从 LCA 到根路径上编号最大的节点。
算法设计：
- 预处理：使用 BFS 从根开始遍历整棵树，计算每个节点的深度、倍增祖先表以及从该节点到根路径上的最大编号（mx数组）。
- 查询处理：对于每个查询，依次计算所有节点的 LCA（通过两两计算），然后输出mx[LCA]。
复杂度：
- 预处理：O(N log N) 时间，O(N log N) 空间。
- 每个查询：O(m log N) 时间，其中 m 是查询的节点数。
- 总体在题目限制下（N ≤ 1e5，Q ≤ 100，m ≤ 1e4）可以高效运行。
注意事项：
- 根节点（0）没有父节点，特殊处理。
- 使用倍增法求 LCA 时，注意处理祖先为 -1 的情况。

代码实现

#include<bits/stdc++.h>usingnamespacestd;constintMAXN=100005;constintLOG=17;// 2^17 > 1e5intn,Q;intfa[MAXN];// 父节点，fa[0] = -1vector<int>g[MAXN];// 孩子列表intdep[MAXN];// 深度intup[MAXN][LOG];// 倍增祖先表intmx[MAXN];// 从当前节点到根路径上的最大编号// 预处理：BFS计算深度、倍增表和mx数组voidpreprocess(){queue<int>q;q.push(0);dep[0]=0;mx[0]=0;// 初始化根节点的倍增表for(intk=0;k<LOG;++k)up[0][k]=-1;while(!q.empty()){intu=q.front();q.pop();for(intv:g[u]){dep[v]=dep[u]+1;mx[v]=max(v,mx[u]);// 路径上最大编号up[v][0]=u;// 计算v的高层祖先for(intk=1;k<LOG;++k){if(up[v][k-1]!=-1)up[v][k]=up[up[v][k-1]][k-1];elseup[v][k]=-1;}q.push(v);}}}// 求两个节点的最近公共祖先intlca(intu,intv){if(dep[u]<dep[v])swap(u,v);// 将u提升到与v同一深度for(intk=LOG-1;k>=0;--k){if(up[u][k]!=-1&&dep[up[u][k]]>=dep[v]){u=up[u][k];}}if(u==v)returnu;// 一起向上跳for(intk=LOG-1;k>=0;--k){if(up[u][k]!=up[v][k]){u=up[u][k];v=up[v][k];}}returnup[u][0];}intmain(){ios::sync_with_stdio(false);cin.tie(0);cin>>n;fa[0]=-1;for(inti=1;i<n;++i){cin>>fa[i];g[fa[i]].push_back(i);}preprocess();cin>>Q;while(Q--){intm;cin>>m;vector<int>s(m);for(inti=0;i<m;++i)cin>>s[i];// 计算所有节点的LCAintans=s[0];for(inti=1;i<m;++i){ans=lca(ans,s[i]);}// 输出该LCA到根路径上的最大编号cout<<mx[ans]<<'\n';}return0;}

功能分析

一、数据结构设计

树存储：
- g[MAXN]：邻接表存储孩子节点
- fa[MAXN]：父节点数组
- dep[MAXN]：节点深度
查询优化结构：
- up[MAXN][LOG]：倍增表，用于快速跳转祖先
- mx[MAXN]：从根节点到当前节点路径上的最大节点编号

二、核心算法

1. 预处理阶段 (`preprocess()`)

使用BFS遍历整棵树
计算每个节点的深度和倍增祖先表
同时计算mx[]数组：mx[v] = max(v, mx[u])
- 表示从根到v路径上的最大节点编号
- 这是一个DP思想，利用了树路径的单调性

2. LCA算法 (`lca()`)

使用倍增法求最近公共祖先
时间复杂度：O(logN)

3. 查询处理

对于每个查询：

输入m个节点
计算这些节点的LCA（依次两两计算）
输出mx[LCA]- 即从根到LCA路径上的最大节点编号

三、时间复杂度总结

预处理：O(NlogN)
Q次查询：O(Q·M·logN)，其中M是查询集合大小

完整GESP C++考级真题题解专栏：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}

2023年12月GESP真题及题解(C++八级): 大量的工作沟通