1 条题解
-
0
【题目大意】0 号是老板,一个人可以管理自己,管理直接下属,管理下属的下属。可以根据关系建立起树结构。现在要求有 m 个人自己组织会议,要找一个人主持会议。如果 m 个人中能主持就从 m 个人中选,不能就找上级领导,有多个选择,就求出最大的编号。注意,参会和主持的角色不一样。每次询问输出多个点的编号最大的公共祖先,本质上就是 LCA 问题。
【考纲知识点】LCA 问题
【解题思路】把每个点的祖先全部求出来,然后用数组标记,如果这个点被标记了 m 次,那就说明这个点是所有员工的公共祖先。
最后输出最大值即可。
【参考程序】
#include <bits/stdc++.h> using namespace std; const int N = 100010; int fa[N], vis[N]; void change(int x) { vis[x]++;//自己能管理自己,即自己是自己的祖先 while(x != 0) { x = fa[x];//一直向上找祖先 vis[x]++;//记录这个点作为祖先的个数 } } int main() { int n; scanf("%d", &n); for (int i = 1; i < n; i++) { scanf("%d", &fa[i]); } int q; scanf("%d", &q); while(q--) { int m; scanf("%d", &m); //注意vis数组要清空 memset(vis, 0, sizeof(vis)); for (int i = 1; i <= m; i++) { int x; scanf("%d", &x); change(x);//每输入一个数,进行标记 } int ans = 0; //因为是从小到大枚举的,所以不用取max for (int i = 1; i < n; i++) { if (vis[i] == m) ans = i; } printf("%d\n", ans); } return 0; }
- 1
信息
- ID
- 580
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 6
- 标签
- 递交数
- 28
- 已通过
- 10
- 上传者