求解释。

这是一个题解的代码 O2 2.9s

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int N=500005;
int n,m,s;
vector<int> e[N];
int dep[N],fa[N][22];

void dfs(int x,int f){ //树增dep,fa
  dep[x]=dep[f]+1; fa[x][0]=f;
  //x上面2,4,8...的祖先fa
  for(int i=1; i<=20; i++) 
    fa[x][i]=fa[fa[x][i-1]][i-1]; 
  for(int y : e[x])
    if(y!=f) dfs(y,x);
}
int lca(int x,int y){ //树增lca
  if(dep[x]<dep[y]) swap(x,y);
  //x先大步后小步向上跳，直到与y同层
  for(int i=20; ~i; i--)
    if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
  if(x==y) return y;
  //x,y一起向上跳，直到lca的下面
  for(int i=20; ~i; i--)
    if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
  return fa[x][0];
}
int main(){
  scanf("%d%d%d",&n,&m,&s); int a,b;
  for(int i=1; i<n; i++){
    scanf("%d%d",&a,&b);
    e[a].push_back(b); e[b].push_back(a);
  }
  dfs(s,0);
  while(m--)
    scanf("%d%d",&a,&b),printf("%d\n",lca(a,b));
}

然而我自以为是的优化了下：对于x和y，设深度差h=dep[x]-dep[y]（>0），先让x向上跳到与y同层。h转成二进制，那么$h=c_0*2^0+c1*2+...c_k*2^k（c_i=0/1）$时，每一个为1的$c_i$都代表向上$2^i$步。 得到4.49s O2 代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5*1e5+5;
int n,m,s;
int dep[N],f[N][21];
vector<int> g[N];
void dfs(int u,int fa)
{
	//cout<<f[2][0]<<endl;
	dep[u]=dep[fa]+1;f[u][0]=fa;/*,cout<<"f"<<u<<":"<<f[u][0]<<endl*/
	for(int i=1;i<=20;i++)
	{
		f[u][i]=f[f[u][i-1]][i-1];
	}
	for(int i:g[u])
	{
		if(i==fa) continue;
		//cout<<i<<" "<<u<<endl;
		dfs(i,u);
	}
}
void lca(int x,int y)
{
	int k=-1;
	if(dep[x]<dep[y]) swap(x,y);
	//cout<<x<<" "<<y<<endl; 
	int h=dep[x]-dep[y];
	//cout<<"h:"<<h<<endl;
	while(h)
	{
		int c=h&1;//c=1
		//cout<<"c:"<<c<<endl;
		k++;//k=0
		//cout<<"k:"<<k<<endl;
		h=h>>1;
		//cout<<"h:"<<h<<endl; 
		if(c) 
		{
			x=f[x][k];//x=f[2][0]=4
			//cout<<x<<endl;
			//if(x==y) return y;
		}	
	}
	//cout<<x<<" "<<y<<endl;
	if(x==y) {cout<<y<<endl;return;} //特判
	/*for(int i=0;i<=20;i++)*/
	for(int i=20;~i;i--)
	{
		if(f[x][i]!=f[y][i]) 
		{
			x=f[x][i],y=f[y][i];
		} 
	} 
	//return f[x][0];
	cout<<f[x][0]<<endl;
}
int main()
{
	cin>>n>>m>>s;
	for(int i=1;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		g[x].push_back({y});
		g[y].push_back({x});
	}
	dfs(s,0);
	//cout<<f[2][0]<<endl;
	for(int i=1;i<=m;i++)
	{
		int a,b;
		cin>>a>>b;
		lca(a,b);//cout<<lca(a,b)<<endl;
	}
 	return 0;
}

我不明白为什么按照深度差准确地跳，会比直接从大到小枚举向上跳要慢呢？