代码求调(悬一关)
查看原帖
代码求调(悬一关)
983702
lrj3247楼主2024/11/9 16:03
#include <bits/stdc++.h>
using namespace std;
inline int read(){
	int w=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while('0'<=ch&&ch<='9'){
		w=w*10+ch-'0';
		ch=getchar();
	}
	return w*f;
}
const int N=3e5+15;
vector <int> e[N];
int zx[N],sum[N],fa[N];
int find(int u,int v){
	int now = v;
	while(now!=u){
		if(sum[now]*2>=sum[u]){
			return now;
		}
	}
	return now;
}
void dfs(int now){
	sum[now]=1,zx[now]=now;
	int len = e[now].size();
	for(int i = 0 ; i<len ; i++){
		int to = e[now][i];
		dfs(to);
		sum[now]+=sum[to];
	}
	for(int i = 0 ; i<len ; i++){
		int to = e[now][i];
		if(sum[to]*2>=sum[now]){
			zx[now]=find(now,to);
		}
	}
	return ;
}
int main(){
	int n=read(),q=read();
	for(int i = 2 ; i<=n ; i++){
		fa[i]=read();
		e[fa[i]].push_back(i);
	}
	dfs(1);
	for(int i = 1 ; i<=q ; i++){
		int u = read();
		cout<<zx[u]<<"\n";
	}
	return 0;
}
2024/11/9 16:03
加载中...