55分求调
查看原帖
55分求调
1633249
YXLISME楼主2025/2/4 06:49

My Code:

#include <bits/stdc++.h>
#define int long long
#pragma GCC optimize ("Ofast")
using namespace std;
int n,i,q,v,m,x,y,e[100010][20],b[100010],ma[100010];
vector<int>f[100010];
void dfs(int x,int fx){
	e[x][0]=fx;b[x]=b[fx]+1;ma[x]=max(x,ma[fx]);
	for(int i=1;i<18;i++) e[x][i]=e[e[x][i-1]][i-1];
	for(int i=0;i<f[x].size();i++){
		int sx=f[x][i];
		if(sx==fx) continue;
		dfs(sx,x);
	}
}
int lca(int x,int y){
	if(b[x]<b[y]) swap(x,y);
	int h=b[x]-b[y];
	for(int i=0;i<18;i++)
		if(h&(1<<i)) x=e[x][i];
	if(x==y) return x;
	for(int i=17;i>=0;i--)
		if(e[x][i]!=e[y][i]) x=e[x][i],y=e[y][i];
	return e[x][0];
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
//	cout<<log2(100000);
	cin>>n;
	for(i=1;i<n;i++) cin>>v,f[i].push_back(v),f[v].push_back(i);
	dfs(0,-1);
	cin>>q;
	while(q--){
		cin>>m>>x;
		while(--m) cin>>y,x=lca(x,y);
		cout<<ma[x]<<"\n";
	}
	return 0;
}

hack数据过来,但是别的错了一大堆 评测信息

2025/2/4 06:49
加载中...