20分LCA求助
查看原帖
20分LCA求助
205782
R浩轩泽Anmicius楼主2021/3/29 17:57

题目尝试分别复制题解里LCA和bfs的代码,还是只能拿到20分。

放一下源代码

//#pragma GCC opitimize(2)
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=5e5+10,X=25;
int n,m,num,head[N],fa[N][X],log_2[X],dep[N];
long long ans;
struct Edge{
	int pre;
	int to;
	int nxt;
}edge[2*N];
inline void add_edge(int x,int y){
	edge[++num].pre=x;
	edge[num].to=y;
	edge[num].nxt=head[x];
	head[x]=num;
}
void dfs(int x,int Fa){
	dep[x]=dep[Fa]+1;
	fa[x][0]=Fa;
	for(register int i=1;(1<<i)<=dep[x];++i)
	fa[x][i]=fa[fa[x][i-1]][i-1];
	for(register int i=head[x];i;i=edge[i].nxt)
	if(edge[i].to!=Fa)dfs(edge[i].to,x);
}
inline int lca(int x,int y){
	if(dep[x]<dep[y])swap(x,y);
	while(dep[x]>dep[y])
	x=fa[x][log_2[dep[x]-dep[y]]-1];
	if(x==y)return x;
	for(register int i=log_2[dep[x]];i>=0;--i)
	if(fa[x][i]!=fa[y][i]){
		x=fa[x][i];y=fa[y][i];
	}
	return fa[x][0];
} 
inline void read(int &x){
	x=0;int f=1;char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=x*10+(ch^48);
		ch=getchar();
	}
	x*=f;
}
signed main(){
	read(n);read(m);
	for(register int i=1;i<=n-1;++i){
		int a,b;
		read(a);read(b);
		add_edge(a,b);
		add_edge(b,a);
	}
	dfs(1,0);
	for(int i=1;i<=n;i++)
	log_2[i]=log_2[i-1]+(1<<log_2[i-1]==i);
	for(register int i=1;i<=m;++i){
		int a,b,c,p1,p2,p3,p;
		read(a);read(b);read(c);
		ans=0;
		p1=lca(a,b);p2=lca(a,c);p3=lca(b,c);
		if(p1==p2)p=p3;
		else if(p2==p3)p=p1;
		else if(p1==p3)p=p2;
		ans=dep[a]+dep[b]+dep[c]-dep[p1]-dep[p2]-dep[p3];
		cout<<p<<' '<<ans<<'\n'; 
	}
	return 0;
}

请问是代码其它部分出了问题吗?

2021/3/29 17:57
加载中...