悬关求调 0pts 样例2都过不了
查看原帖
悬关求调 0pts 样例2都过不了
1080289
202312904614lcx楼主2024/5/14 16:47
#include<bits/stdc++.h>
using namespace std;
int lg[500010];
int fa[500010][20];
int depth[500010];
struct node{
	int next,to;
};node edge[500010 << 1];
int head[500010];
int cnt=1;
void add(int a,int b){
	edge[cnt].to=b;
	edge[cnt].next=head[a];
	head[a]=cnt++;
}
void dfs(int now,int father){
	fa[now][0]=father,depth[now]=depth[father]+1;
	for(int i=1;i<=lg[depth[now]];i++){
		fa[now][i]=fa[fa[now][i-1]][i-1];
	}
	for(int i=head[now];i;i=edge[i].next){
		if(edge[i].to!=father){
			dfs(edge[i].to,now);
		}
	}
}
int lca(int x,int y){
	if(depth[x]<depth[y]){
		swap(x,y);
	}
	while(depth[x]>depth[y]){
		x=fa[x][lg[depth[x]-depth[y]]-1];
	}
	if(x==y){
		return x;
	}
	for(int k=lg[depth[x]]-1;k>=0;k--){
		if(fa[x][k]!=fa[y][k]){
			x=fa[x][k];
			y=fa[y][k];
		}
	}
	return fa[x][0];
}
 int main(){
 	int n;
 	cin>>n;
 	for(int i=1;i<=n-1;i++){
 		int x;
 		cin>>x;
 		add(x,i);
 		add(i,x);
	 }
	 int t;
	 cin>>t;
	 dfs(0,0);
	 for(int i=1;i<=n;i++){
	 	lg[i]=lg[i>>1]+1;
	 }
	 while(t--){
	 	int m;
	 	cin>>m;
	 	int f;
	 	cin>>f;
	 	for(int i=1;i<=m-1;i++){
	 		int x;
	 		cin>>x;
	 		f=lca(f,x); 
		 }
		 int ans=f;
		 while(f!=0){
		 	ans=max(ans,fa[f][0]);
		 	f=fa[f][0];
		 }
		 cout<<ans<<endl;
	 }
	 return 0;
 }
2024/5/14 16:47
加载中...