RT 两份代码 ，第一个AC ，第二个WA20分（并且无法正确更新倍增数组f） ，但是感觉两个都没有问题 ，有大佬解释一下吗 （两个代码的区别只在于初始化 f 数组一个放在dfs里， 一个放在init里）

这个是AC的

#include<iostream>
#include<cstdio>
#define maxn 500005
using namespace std;

struct Edge{
	int v,next;//终点 下一条边 
}edge[maxn<<1]; 
int n,m,s,cnt,head[maxn],f[maxn][21],dep[maxn];

inline int read(){ 
	char cc=getchar();
	int ans=0;
	int f=1;
	while (cc<'0'||cc>'9'){
		if (cc=='-') {
			f=-1;
		}
		cc=getchar();
	}
	while (cc>='0'&&cc<='9'){
		ans=(ans<<3)+(ans<<1)+cc-'0';
		cc=getchar();
	}
	return ans*f;
}

void add(int u,int v){
	edge[++cnt].v=v;
	edge[cnt].next=head[u];
	head[u]=cnt;
}

void dfs(int u,int fa){
	dep[u]=dep[fa]+1;f[u][0]=fa;
	for (int i=1;(1<<i)<=dep[u];i++){
		f[u][i]=f[f[u][i-1]][i-1];
	}
	for (int i=head[u];i;i=edge[i].next){
		int v=edge[i].v;
		if (v==fa) continue;
		dfs(v,u);
	}
}

int lca(int x,int y){
	if (dep[x]<dep[y]) swap(x,y);
	//1.跳到同一层 
	if (dep[x]!=dep[y]){
		for (int step=20;step>=0;step--){
			if (dep[x]-(1<<step)>=dep[y]){
				x=f[x][step];
			}
			if (dep[x]==dep[y]) break;
		}
	}
	if (x==y) return x;
	//2.同层一起跳 
	for (int same_step=20;same_step!=-1;same_step--){
		if (f[x][same_step]!=f[y][same_step]){
			x=f[x][same_step];
			y=f[y][same_step];
		}
	}
	return f[x][0];
}

int main(){
	n=read();m=read();s=read();
	int x,y;
	for (register int i=1;i<n;i++){
		x=read();y=read();
		add(x,y);
		add(y,x);
	}
	dfs(s,0);
	for (register int i=1;i<=m;i++){
		x=read();y=read();
		printf("%d\n",lca(x,y));
	}
	return 0;
}

这个是WA的

#include<iostream>
#include<cstdio>
#define maxn 500005
using namespace std;

struct Edge{
	int v,next;//终点 下一条边 
}edge[maxn<<1]; 
int n,m,s,cnt,head[maxn],f[maxn][21],dep[maxn];

inline int read(){ 
	char cc=getchar();
	int ans=0;
	int f=1;
	while (cc<'0'||cc>'9'){
		if (cc=='-') {
			f=-1;
		}
		cc=getchar();
	}
	while (cc>='0'&&cc<='9'){
		ans=(ans<<3)+(ans<<1)+cc-'0';
		cc=getchar();
	}
	return ans*f;
}

void add(int u,int v){
	edge[++cnt].v=v;
	edge[cnt].next=head[u];
	head[u]=cnt;
}

void dfs(int u,int fa){
	dep[u]=dep[fa]+1;f[u][0]=fa;
	for (int i=head[u];i;i=edge[i].next){
		int v=edge[i].v;
		if (v==fa) continue;
		dfs(v,u);
	}
}

void init(){
	for (register int i=1;i<=n;i++){
		for (register int j=1;(1<<j)<=dep[i];j++){
			f[i][j]=f[ f[i][j-1] ][j-1];
			//分成两端跳 
		}
	}
}

int lca(int x,int y){
	if (dep[x]<dep[y]) swap(x,y);
	//1.跳到同一层 
	if (dep[x]!=dep[y]){
		for (int step=20;step>=0;step--){
			if (dep[x]-(1<<step)>=dep[y]){
				x=f[x][step];
			}
			if (dep[x]==dep[y]) break;
		}
	}
	if (x==y) return x;
	//2.同层一起跳 
	for (int same_step=20;same_step!=-1;same_step--){
		if (f[x][same_step]!=f[y][same_step]){
			x=f[x][same_step];
			y=f[y][same_step];
		}
	}
	return f[x][0];
}

int main(){
	n=read();m=read();s=read();
	int x,y;
	for (register int i=1;i<n;i++){
		x=read();y=read();
		add(x,y);
		add(y,x);
	}
	dfs(s,0);
   init();
	for (register int i=1;i<=m;i++){
		x=read();y=read();
		printf("%d\n",lca(x,y));
	}
	return 0;
}