关于倍增求LCA
  • 板块学术版
  • 楼主AAA404
  • 当前回复8
  • 已保存回复8
  • 发布时间2023/5/24 19:02
  • 上次更新2023/10/23 14:52:12
查看原帖
关于倍增求LCA
723198
AAA404楼主2023/5/24 19:02

rt,我在洛谷外的某一OJ提交时,取得了以下成绩:

CE 1(这个是手残)

RE 17(这个是我要说的)

但在洛谷上提交就AC了(虽然常数有点大)

在本地运行洛谷数据也会RE

调试发现RE在一个很神奇的地方(见代码注释)

还有手调了一个大数据,发现好像会无限递归然后爆栈(?

#include<bits/stdc++.h>
using namespace std;
const int N=5e6+5;
int n,m,s,f[N][30],dep[N];
vector<int>v[N];
inline int read()
{
	char ch=getchar();int s=0,w=1;
	while(ch<'0' || ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0' && ch<='9'){s=s*10+ch-48;ch=getchar();}
	return s*w;
}
inline void dfs(int step,int faa)
{
	dep[step]=dep[faa]+1;
	f[step][0]=faa;
	for(int i=1;(1<<i)<=dep[step];i++)
	{
		f[step][i]=f[f[step][i-1]][i-1];
	}
	for(int t:v[step])//RE在这里
	{
		if(t!=faa)
		dfs(t,step);
	}
}
inline int LCA(int u,int v)
{
	if(dep[u]<dep[v])swap(u,v);
	for(int i=20;i>=0;i--)
	{
		if(dep[f[u][i]]>=dep[v])u=f[u][i];
	}
	if(u==v)return v;
	for(int i=20;i>=0;i--)
	{
		if(f[u][i]!=f[v][i])u=f[u][i],v=f[v][i];
	}
	return f[u][0];
}
int main()
{
//	freopen("1.in","r",stdin);
 //	freopen("1.out","w",stdout);
 	n=read(),m=read(),s=read();
 	for(int i=1;i<=n-1;i++)
 	{
 		int a=read(),b=read();
 		v[a].push_back(b);
 		v[b].push_back(a);
	}
	dfs(s,0);
	for(int i=1;i<=m;i++)
	{
		int a=read(),b=read();
		cout<<LCA(a,b)<<endl;
	}
 	return 0;
}

救救孩子吧,孩子调这一题调两天了

但是链式前向星不会RE,但是我习惯写vector,而且其他题用vector也没RE

2023/5/24 19:02
加载中...