LCA模板能过,但本题LCA出错?
查看原帖
LCA模板能过,但本题LCA出错?
549521
boy♂Next♂dooor楼主2024/7/30 15:46

该题代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,Q;
vector<int> g[N];
int f[N][17],dep[N];
void dfs(int x,int from)
{
	dep[x]=dep[from]+1;f[x][0]=from;
	for(int i=1;i<=17;i++)
	{
		f[x][i]=f[f[x][i-1]][i-1];
	}
	for(auto v:g[x])
	{
		if(v==from) continue;
		dfs(v,x);
	}	
}
int lca(int x,int y)
{
	if(dep[x]<dep[y]) swap(x,y);
	int k=-1;
	int h=dep[x]-dep[y];
	while(h)
	{
		int c=h&1;
		k++;
		h=h>>1;
		if(c) x=f[x][k];
	}
	if(x==y) return y;
	for(int i=17;~i;i--)
	{
		if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
	}
	return f[x][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;
		g[i].push_back({x});
		g[x].push_back({i});
	}
	memset(f,-1,sizeof(f));
	dfs(0,-1);
	//cout<<lca(3,4);
	cin>>Q;	
	for(int i=1;i<=Q;i++)
	{
		int m;
		cin>>m;
		int x,y;
		cin>>x>>y;
		y=lca(x,y);
		for(int j=3;j<=m;j++) 
		{
			int a;
			cin>>a;
		}
		for(int i=y;~i;i=f[y][0])
		{
			y=max(y,i);
		} 	
	}
 	return 0;
}

如果把注释改代码,就会发现按样例1 输入,得到lca(3,4)=-1,正确应该是2。 LCA错了?然而模板能过

2024/7/30 15:46
加载中...