100分WA一点求调
查看原帖
100分WA一点求调
744895
liaoxingrui楼主2024/3/29 16:29
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,x,a,b,tot,cnt;
int fa[N],dep[N],siz[N],son[N],dfn[N],top[N],head[N];
struct node{
	int xx,yy;
}next[N<<1];
inline void add(int x,int y){
	tot++;
	next[tot].xx=y;
	next[tot].yy=head[x];
	head[x]=tot;
}
inline void dfs1(int node){
	siz[node]=1;
	int ma=0;
	for(int i=head[node];i;i=next[i].yy){
		int w=next[i].xx;
		if(w!=fa[node]){
			fa[w]=node;
			dep[w]=dep[node]+1;
			dfs1(w);
			siz[node]+=siz[w];
			if(siz[w]>ma){
				son[node]=w;
				ma=siz[w]; 
			}
		}
	}
}
inline void dfs2(int node,int t){
	cnt++;
	dfn[node]=cnt;
	top[node]=t;
	if(!son[node])
		return;
	dfs2(son[node],t);
	for(int i=head[node];i;i=next[i].yy){
		int w=next[i].xx;
		if(w!=fa[node]&&w!=son[node])
			dfs2(w,w);
	}
}
inline int Lca(int x,int y){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])
			swap(x,y);
		x=fa[top[x]];
	}
	return (dep[x]<dep[y]?x:y);
}
int main(){
	cin>>n;
	for(int i=1;i<n;i++){
		cin>>x;
		add(x,i);
		add(i,x);
	}
	dfs1(0);
	dfs2(0,0);
	cin>>m;
	while(m--){
		cin>>n;
		int mi=1e9,ma=0;
		while(n--){
			cin>>x;
			if(dfn[x]>ma){
				ma=dfn[x];
				a=x;
			}
			if(dfn[x]<mi){
				mi=dfn[x];
				b=x;
			}
		}
		cout<<Lca(a,b)<<endl;
	}
	return 0;
}
2024/3/29 16:29
加载中...