板子题目链接

#include <bits/stdc++.h>
using namespace std;
int n,m,s;
const int N=5e5+10;
int f[N][21];
int d[N];
void st(){
	for(int j=1;j<=21;j++){
		for(int i=1;i<=n;i++){
			f[i][j]=f[f[i][j-1]][j-1];
		}
	}
}
int head[N],ver[N],ne[N],tot=0;
void add(int u,int v){
	ver[++tot]=v;
	ne[tot]=head[u];
	head[u]=tot;
}
int lca(int x,int y){
	if(d[x]>d[y]){
		swap(x,y);
	}
	for(int i=21;i>=0;i--){
		if(d[f[y][i]]>=d[x]){
			y=f[y][i];
		}
	}
	if(x==y){
		return x;
	}
	for(int i=21;i>=0;i--){
		if(f[y][i]!=f[x][i]){
			x=f[x][i];
			y=f[y][i];
		}
	}
	return f[x][0];
}
bool vis[N];
void dfs(int k,int dis,int fa){
	d[k]=dis;
	vis[k]=1;
	if(fa==0)f[k][0]=k;
	else f[k][0]=fa;
//	cout<<"--";
//	cout<<v[k].size();
	for(int i=head[k];i;i=ne[i]){
		int j=ver[i];
		if(vis[j])continue;
		vis[j]=1;
	//	cout<<k<<"->"<<j<<endl;
		dfs(j,dis+1,k);
	}
	return ;
}
int main(){
	memset(d,0,sizeof d);
	memset(vis,0,sizeof vis);
	cin>>n>>m>>s;
	for(int i=1;i<=n-1;i++){
		int x,y;
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	dfs(s,0,0);
	st();
//	for(int i=1;i<=n;i++){
//		cout<<i<<": "<<d[i]<<endl;
//	}
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		cout<<lca(x,y)<<endl;
	}
	return 0;
}

问题疑似出现在st表？