玄关求调 60ptsMLE
查看原帖
玄关求调 60ptsMLE
784175
zhujiajun2013楼主2024/9/16 17:07
#include<bits/stdc++.h>
using namespace std;
const int N=5e6+5;
int n,r[5000005],cnt,head[5000005],fa[5000005],t,ans[N];
struct node{
	int to,nxt;
}a[500005];
inline int read(){
	int s=0;char c=getchar();
	while(!isdigit(c))  c=getchar();
	while(isdigit(c))  s=(s<<3)+(s<<1)+(c^48),c=getchar();
	return s;
}
template<typename T>
inline void write(T x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');return;
}
void add(int u,int v){
	a[cnt].to=v;
	a[cnt].nxt=head[u];
	head[u]=cnt++;
}
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
void dfs(int u,int to){
	r[u]=r[to]+1;
	for(register int i=head[u];~i;i=a[i].nxt){
		int v=a[i].to;
		dfs(v,u);
		fa[v]=u;
	}  
	if(ans[r[u]])ans[r[u]]=find(ans[r[u]]);
	else ans[r[u]]=u;
}
int main(){
	n=read();t=read();
	memset(head,-1,sizeof head);
	for(register int i=1;i<=n;i++){
		fa[i]=i;
		int x;
		x=read();
		add(x,i);
	}
	dfs(1,0);
	while(t--){
		int x;
		x=read();
		write(ans[x]);
		printf("\n");
	}
	return 0;
}
2024/9/16 17:07
加载中...