题目尝试分别复制题解里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;
}
请问是代码其它部分出了问题吗?