自动搬运

查看原文

来自洛谷，原作者为

	WsW_ 欢迎入群872763867||题解求赞！题解看不懂请私信

搬运于2025-08-24 22:54:45，当前版本为作者最后更新于2024-01-30 00:37:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

难度约为橙到黄。

本题解是目前题解区最精简的题解。

思路

对于每次合作：
假设合作的员工中有 $x$，那么 $x$ 所有的领导都有可能成为主持者，给这些人的标记加一。
如果某个人的标记数等于 $m$，说明他是所有合作者的领导，那么他就可以当主持者。
在所有主持者中找到编号最大的即可。

可以使用 dfs 来遍历某个人所有的领导。

记得每次处理合作前要清空标记。

时间复杂度为 $O(QN^2)$。

代码

#include<bits/stdc++.h>
using namespace std;
int n,q,m,ans;
int f[300];
int cnt[300];
void dfs(int x){
	++cnt[x];
	if(f[x]!=x)dfs(f[x]);//如果直接领导不是自己，就向上遍历
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<n;i++)cin>>f[i];
	cin>>q;
	while(q--){
		memset(cnt,0,sizeof(cnt));
		ans=0;
		cin>>m;
		for(int i=1;i<=m;i++){
			int x;  cin>>x;
			dfs(x);
		}
		for(int i=1;i<n;i++)if(cnt[i]==m)ans=i;
		cout<<ans<<'\n';
	}
	return 0;
}