TLE50求助
查看原帖
TLE50求助
742275
_czy楼主2024/2/28 18:54
#include<iostream>
using namespace std;
#define N 100001
int n,fa[N],h[N],cnt,q,m,x,y,ma[N],dep[N],tp[N],son[N],sz[N];
struct edge{
	int t,u;
}a[N];
void dfs(int x,int mx){
	for(int i=h[x];i;i=a[i].t){
		int u=a[i].u;
		dep[u]=dep[x]+1,ma[u]=max(u,ma[x]);
		dfs(u,ma[u]);
		sz[x]+=sz[u];
		if(!son[x]||sz[son[x]]<sz[u])son[x]=u;
	}
}
void dfs(int x){
	tp[x]=x;
	if(son[fa[x]]==x)tp[x]=tp[fa[x]];
	for(int i=h[x];i;i=a[i].t)dfs(a[i].u);
}
int lca(int x,int y){
	while(tp[x]!=tp[y]){
		if(dep[tp[x]]>dep[tp[y]])x=fa[tp[x]];
		else y=fa[tp[y]];
	}
	return dep[x]<dep[y]?x:y;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=2;i<=n;i++){
		cin>>fa[i];
		a[++cnt].u=i,a[cnt].t=h[++fa[i]],h[fa[i]]=cnt;
	}
	ma[1]=1;
	dfs(1,1);
	dfs(1);
	cin>>q;
	while(q--){
		cin>>m>>x;
		x++;
		for(int i=2;i<=m;i++){
			cin>>y;
			x=lca(x,y+1);
		}
		cout<<ma[x]-1<<'\n';
	}
}
2024/2/28 18:54
加载中...