在此之前，我写过另一篇博客，是倍增（在线）求LCA。有兴趣的同学可以去看一看。概念以及各种暴力就不在这里说了，那篇博客已经有介绍了。
不会ST算法的同学点这里
ST（RMQ）算法在线求LCA
这个算法的思想，就是将LCA问题转化成RMQ问题。
怎么将LCA转成RMQ？
我们首先用dfsO(N)遍历一遍。比如下图：
得到一个dfs序（从儿子回到父亲也要算一遍）：
1->2->4->7->4->8->4->2->5->2->6->9->6->10->6->2->1->3->1
可以简单地理解成这样：你一开始在根节点，一直向下走，发现尽头就倒退，向另一个方向走。最后你还会回到根节点。你遍历这个树的顺序就是一个这样的dfs序。
有没有发现什么规律?
设r[x]表示x在这个dfs序当中第一次出现的位置，deep[x]表示x的深度。
那么可以发现，如果要求x和y的LCA，r[x]~r[y]这一段区间内一定有它们的LCA，而且还是区间中深度最小的那个。
这是为什么？
只要你懂dfs，简单思考一下就能明白。到达x点后，再到y点，必须经过过它们的LCA，因为这是一棵树，两个点之间有且只有一条路径。
为什么它在区间中深度最小？
因为dfs的原因，遍历以LCA(x,y)为根的子树时，不遍历完所有以LCA(x,y)为根的点是不会回去的。然而x、y一定在以LCA(x,y)为根的子树当中，所以这也是成立的。
具体怎么做?
首先，用dfsO(n)求出dfs序、r数组和deep数组。
然后，套一个纯的ST（RMQ）。设f[i][j]表示j~j+2^i-1的点当中，deep值最小的是哪个。
预处理做完了，接下来就可以在线O(1)回答询问了。
注意事项
这个dfs序长度是2n-1的，原因：每个点经过的次数=儿子个数+1。那么所有点的儿子个数一共有n-1，因为没有根节点。所有是2n-1的。
在线O(1)回答的时候，有的人求对数使用log(x)/log(2)的形式。实际上没必要，因为C++中有个东西叫log2，直接用就好。
代码实现
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
int n,_n,m,s;//_n是用来放元素进dfs序里，最终_n=2n-1
struct EDGE
{
int to;
EDGE* las;
} e[1000001];//前向星存边
EDGE* last[500001];
int sx[1000001];//顺序，为dfs序
int f[21][1000001];//用于ST算法
int deep[500001];//深度
int r[500001];//第一次出现的位置
void dfs(int,int,int);
int min(int a,int b){return deep[a]<deep[b]?a:b;}
int query(int,int);
int main()
{
scanf("%d%d%d",&n,&m,&s);
int i,j=0,x,y;
for (i=1;i<n;++i)
{
scanf("%d%d",&x,&y);
e[++j]={y,last[x]};
last[x]=e+j;
e[++j]={x,last[y]};
last[y]=e+j;
}
dfs(s,0,0);
//以下是ST算法
for (i=1;i<=_n;++i)
f[0][i]=sx[i];
int ni=int(log2(_n)),nj,tmp;
for (i=1;i<=ni;++i)
{
nj=_n+1-(1<<i);
tmp=1<<i-1;
for (j=1;j<=nj;++j)
f[i][j]=min(f[i-1][j],f[i-1][j+tmp]);
}
//以下是询问，对于每次询问，可以O(1)回答
while (m--)
{
scanf("%d%d",&x,&y);
printf("%d\n",query(r[x],r[y]));
}
}
void dfs(int t,int fa,int de)
{
sx[++_n]=t;
r[t]=_n;
deep[t]=de;
EDGE* ei;
for (ei=last[t];ei;ei=ei->las)
if (ei->to!=fa)
{
dfs(ei->to,t,de+1);
sx[++_n]=t;
}
}
int query(int l,int r)
{
if (l>r)
{
//交换
l^=r;
r^=l;
l^=r;
}
int k=int(log2(r-l+1));
return min(f[k][l],f[k][r-(1<<k)+1]);
}