求调!100pts但是被hack
查看原帖
求调!100pts但是被hack
654763
smallpeople楼主2024/10/23 15:16
#include<bits/stdc++.h>
using namespace std;

int n,q,m;
int a[10005],dep[100005],f[100005][65];
vector <int> p[100005];

void dfs(int u)
{
	for(int i = 0;i < p[u].size();i ++)
	{
		int v = p[u][i];
		dep[v] = dep[u] + 1;
		dfs(v);
	}
}

void getparents()
{
	for(int j = 1;(1 << j) <= n;j ++)
		for(int i = 1;i < n;i ++)
			f[i][j] = f[f[i][j - 1]][j - 1];
}

int lca(int u,int v)
{
	if(dep[u] < dep[v])swap(u,v);
	int i = -1,j;
	while((1 << (i + 1)) <= dep[u])i ++;
	
	for(j = i;j >= 0;j --)
		if(dep[u] - (1 << j) >= dep[v])u = f[u][j];
	
	if(u == v)return u;
	
	for(j = i;j >= 0;j --)
		if(f[u][j] != f[v][j])
		{
			u = f[u][j];
			v = f[v][j];
		}
	
	return f[u][0];
}

int main()
{	
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n;
	for(int i = 1;i < n;i ++)
	{
		int x;
		cin>>x;
		p[x].push_back(i);
		f[i][0] = x;
	}
	
	//倍增lca预处理 
	dfs(0);
	getparents();
	
	cin>>q;
	while(q --)
	{
		cin>>m;
		for(int i = 1;i <= m;i ++)
			cin>>a[i];
		
		int i = 3,x = lca(a[1],a[2]);
		while(i <= m)
		{
			x = lca(x,a[i]);
			i ++;
		}
		cout<<x<<'\n';
	}
	return 0;
}
2024/10/23 15:16
加载中...