82 lines
2.0 KiB
C++
82 lines
2.0 KiB
C++
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
const int N = 310; // 最多300个点
|
||
const int M = 310; // 最多299条边，因为它是树，300个点，其实是299条边
|
||
|
||
// 链式前向星
|
||
int e[M], h[N], idx, w[M], ne[M];
|
||
void add(int a, int b, int c = 0) {
|
||
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
|
||
}
|
||
int n;
|
||
|
||
set<int> a[N]; // 节点i可以管理的节点集合
|
||
|
||
// 树的深度优先搜索代码
|
||
void dfs(int u) { // 以u为根的子树的节点数量
|
||
// 遍历一下当前点的所有出边
|
||
for (int i = h[u]; i != -1; i = ne[i]) { // i是遍历 u的每条出边
|
||
int j = e[i]; // j是u的出边指向的节点
|
||
// 递归处理j
|
||
dfs(j);
|
||
// 针j中的所有孩子记录到u中去,注意：这个合并是要在dfs之后，因为dfs是先递归到最深，然后回溯
|
||
for (auto x : a[j])
|
||
a[u].insert(x);
|
||
}
|
||
}
|
||
|
||
int main() {
|
||
#ifndef ONLINE_JUDGE
|
||
freopen("20231202_2.in", "r", stdin);
|
||
#endif
|
||
|
||
// 初始化链式前向星
|
||
memset(h, -1, sizeof h);
|
||
|
||
cin >> n;
|
||
// 构建单位的管理结构树
|
||
for (int i = 1; i < n; i++) { // 0号是老板
|
||
int f;
|
||
cin >> f;
|
||
add(f, i); // 表示i号员工的领导是f
|
||
a[f].insert(i); // f是i的领导
|
||
}
|
||
|
||
// 自己可以管理自己
|
||
for (int i = 0; i < n; i++)
|
||
a[i].insert(i);
|
||
|
||
// 递归一遍树
|
||
dfs(0);
|
||
|
||
int q;
|
||
cin >> q;
|
||
while (q--) {
|
||
int m;
|
||
cin >> m;
|
||
set<int> s; // 需要处理哪些人员集合
|
||
for (int i = 1; i <= m; i++) {
|
||
int x;
|
||
cin >> x;
|
||
s.insert(x);
|
||
}
|
||
|
||
// // 从n-1到0，找到第一个包含s的集合
|
||
for (int i = n - 1; i >= 0; i--) {
|
||
// 检查s中的每个元素是否都在a[i]中
|
||
bool flag = true;
|
||
for (auto x : s) {
|
||
if (a[i].find(x) == a[i].end()) {
|
||
flag = false;
|
||
break;
|
||
}
|
||
}
|
||
// 如果s中的所有元素都在a[i]中，则i是答案
|
||
if (flag) {
|
||
cout << i << endl;
|
||
break;
|
||
}
|
||
}
|
||
}
|
||
return 0;
|
||
} |