第二个点就错了,报错信息:
Wrong Answer. wrong answer On line 24153 column 1, read 4, expected 2.
好像问题不是很大,但是有点麻烦,谁有类似经历吗?或者哪位数据结构大佬能帮我看一下代码?谢谢!
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int n,q,s,m;
int u[1000005],v[1000005],before[1000005],now[1000005],fa[500005][20],depth[500005];
int max_log=0;
void dfs(int x,int fath){
fa[x][0]=fath;
depth[x]=depth[fath]+1;
for(int i=1;i<=max_log;i++){
fa[x][i]=fa[fa[x][i-1]][i-1];
}
for(int i=now[x];i!=-1;i=before[i]){
if(v[i]!=fath)
dfs(v[i],x);
}
return;
}
int lca(int a,int b){
if(depth[a]<depth[b])
swap(a,b);
for(int i=max_log;i>=0;i--)
if(depth[fa[a][i]]>=depth[b])
a=fa[a][i];
if(a==b)
return a;
for(int i=max_log;i>=0;i--){
if(fa[a][i]!=fa[b][i]){
a=fa[a][i];
b=fa[b][i];
}
}
return fa[a][0];
}
int main(){
cin>>n>>q>>s;
m=n-1;
for(int i=1;i<=n;i++)
for(int j=1;j<=20;j++)
fa[i][j]=i;
memset(now,-1,sizeof(now));
for(int i=1;i<=m;i++){
cin>>u[i]>>v[i];
before[i]=now[u[i]];
now[u[i]]=i;
}
for(int i=m;i<=2*m;i++){
u[i]=v[i-m];
v[i]=u[i-m];
before[i]=now[u[i]];
now[u[i]]=i;
}
depth[s]=1;
while(pow(2,max_log)<n)
max_log++;
dfs(s,s);
while(q--){
int a,b;
cin>>a>>b;
cout<<lca(a,b)<<endl;
}
return 0;
}