我从后缀排序衍生出的 height 数组中找到灵感。

令 $id_i$ 表示 dfs 序为 $i$ 的点。 类似于 height 地，我们构建 $h$ 数组，其中 $h_i = \operatorname{lca}(id_i,id_{i-1})$。

我们不难发现 $h_i = fa_{id_i}$ ，所以对其建立 ST 表就可以做到 $O(1)$ 在线查询了。

这种方法的优点是码量、实现难度小，并且在各种方面碾压欧拉序 LCA。

我难道发现了新的算法？

#include <bits/stdc++.h>
using namespace std;

#define Log(n) (31-__builtin_clz(n))
const int N = 500005;
int n,m,rt,dfn[N],id[N],tot;
int dep[N], f[N], st[N][20];
vector<int>v[N];

int merge(int x,int y) {
	return dep[x]<dep[y] ? x:y;
}
void dfs(int fa,int x) {
	id[dfn[x]=++tot] = x;
	for(int y:v[x]) if(y!=fa)
		dep[y] = dep[x]+1,
		f[y] = x, dfs(x,y);
}
int lca(int x,int y) {
	if(x==y) return x;
	x = dfn[x], y = dfn[y];
	if(x>y) x^=y^=x^=y; x++;
	int tmp = Log(y-x+1);
	return merge(st[x][tmp], st[y-(1<<tmp)+1][tmp]);
}

int main() {
	
	scanf("%d%d%d",&n,&m,&rt);
	for(int i=1,x,y;i<n;i++) {
		scanf("%d%d",&x,&y);
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(0,rt);
	for(int i=2;i<=n;i++)
		st[i][0] = f[id[i]];
	for(int j = 1;j<=Log(n);j++)
		for(int i =1;i<=n-(1<<j)+1;i++)
			st[i][j] =
				merge( st[i][j-1], st[i+(1<<(j-1))][j-1] );
	while(m--) {
		int a,b; scanf("%d%d",&a,&b);
		printf("%d\n",lca(a,b));
	}
	
	return 0;
}