就是把LCA问题转化为RMQ问题
转化之前先要了解欧拉序列：对一棵树进行 DFS，无论是第一次访问还是回溯，每次到达一个结点时都将编号记录下来，可以得到一个长度为 2n-1 的序列，这个序列被称作这棵树的欧拉序列。
比如下面这个树：(2连3和4)
1->2->3
->4->5
其序列就是1 2 3 2 4 5 4 2 1，共九个
记录下每个结点第一次出现的位置，也就是1 2 3 5 6
和树链剖分的思路有点类似，对于给出的u，v，两点间深度最小的点就是LCA
只不过这里两点间也就是欧拉序列包含这两点的这段区间
也记下序列对应的深度，1 2 3 2 3 4 3 2 1
那么用st表记下2^k区间内深度最小的结点号，查询时比较深度即可
例题 洛谷P3379 【模板】最近公共祖先（LCA）
https://www.luogu.com.cn/problem/P3379
#include<iostream>
#include<vector>
#include<cmath>
#define forup(i,l,r) for(int i=l;i<=r;i++)
using namespace std;
const int N=5e5+5;
vector<int> child[N];//结点连接的结点（包含父结点）
int dep[N];//深度
int st[2*N][20];//i开始2^k区间中深度最小的点
int pos[N];//第一次出现的位置
int lg[2*N];
int tot;//序列中的编号
inline int read()
{
int n=0;
char m=getchar();
while(m<'0'||m>'9') m=getchar();
while(m>='0'&&m<='9')
{
n=(n<<1)+(n<<3)+(m^'0');
m=getchar();
}
return n;
}
void dfs(int father,int u)
{
dep[u]=dep[father]+1;
st[++tot][0]=u;
if(!pos[u]) pos[u]=tot;//存第一次出现的位置
for(int x:child[u])
{
if(x!=father)
{
dfs(u,x);
st[++tot][0]=u;//回溯也要记入序列
}
}
}
void ST()
{
int p=lg[tot];
forup(k,1,p)
{
forup(i,1,tot-(1<<k)+1)
{
if(dep[st[i][k-1]]<dep[st[i+(1<<(k-1))][k-1]]) st[i][k]=st[i][k-1];//取深度较小的编号
else st[i][k]=st[i+(1<<(k-1))][k-1];
}
}
}
int query(int l,int r)
{
if(l>r) swap(l,r);//区间嘛，l<=r
int p=lg[r-l+1];
if(dep[st[l][p]]<dep[st[r-(1<<p)+1][p]]) return st[l][p];
else return st[r-(1<<p)+1][p];
}
int main()
{
int n,m,root;
cin>>n>>m>>root;
forup(i,1,n-1)
{
int u=read(),v=read();
child[u].push_back(v);
child[v].push_back(u);
}
dfs(0,root);//求欧拉序列
forup(i,2,tot) lg[i]=lg[i/2]+1;//初始化lg数组
ST();//建st表
forup(i,1,m)
{
cout<<query(pos[read()],pos[read()])<<endl;
}
return 0;
}
当然也可以用pair或结构体让st同时存深度和编号，看个人喜好