LCA问题详解
好久以前写的，也没用latex啥的，一直忘了放出来。（好像是noip前
离线算法 Tarjan
利用并查集优越的时空复杂度，我们可以实现LCA问题的O(n+Q)算法，这里Q表示询问的次数。
Tarjan算法基于深度优先搜索的框架，对于新搜索到的一个结点，首先创建由这个结点构成的集合，再对当前结点的每一个子树进行搜索，每搜索完一棵子树，则可确定子树内的LCA询问都已解决。其他的LCA询问的结果必然在这个子树之外，这时把子树所形成的集合与当前结点的集合合并，并将当前结点设为这个集合的祖先。之后继续搜索下一棵子树，直到当前结点的所有子树搜索完。这时把当前结点也设为已被检查过的，同时可以处理有关当前结点的LCA询问，如果有一个从当前结点到结点v的询问，且v已被检查过，则由于进行的是深度优先搜索，当前结点与v的最近公共祖先一定还没有被检查，而这个最近公共祖先的包涵v的子树一定已经搜索过了，那么这个最近公共祖先一定是v 所在集合的祖先。
这种算法在询问少的时候比较优越。但是我觉得不大实用就没写。
在线ST+dfs
RMQ(Range Minimum/Maximum Query)问题是求区间最值问题。可以写一个线段树，但是预处理和查询的复杂度都是O（logn)。这里有更牛的算法，就是ST（Sparse Table）算法，它可以做到O(nlogn)的预处理，O(1)地回答每个询问。
来看一下ST算法是怎么实现的(以最大值为例）：
首先是预处理，用一个DP解决。设a[i]是要求区间最值的数列，f[i,j]表示从第i个数起连续2j个数中的最大值。例如数列
3 2 4 5 6 8 1 2 9 7
f[1，0]表示第1个数起，长度为20=1个数中的最大值，其实只有3这个数。f[1，2]=5，f[1，3]=8，f[2，0]=2，f[2，1]=4……从这里可以看出f[i,0]其实就等于a[i]。这样，Dp的状态、初值都已经有了，剩下的就是状态转移方程。我们把f[i，j]的求值区间平均分成两段（因为2j一定是偶数），从i到i+2j-1-1为一段，i+2j-1到i+2j-1为一段(长度都为2j-1)。用上例说明，当i=1，j=3时就是3,2,4,5 和 6,8,1,2这两段。f[i，j]就是这两段的最大值中的最大值。于是我们得到了动规方程
f[i][j]=max(f[i][j-1],f[i+2j-1][j-1])
F[i,j]表称为稀疏表（Sparse Table）。有了稀疏表，我们就可以做到O(1)时间查询任意区间的最值。如在上例中我们要求区间[2，8]的最大值，就要把它分成[2,5]和[5,8]两个区间，因为这两个区间长度为22，最大值我们可以直接由f[2，2]和f[5，2]得到。扩展到一般情况，就是把区间[l，r]分成两个长度为2j的区间（保证有f[i，j]对应，其中2j为小于r-l+1的最大值）。即，q[l,r] 表示 从第l个数到第r个数中最大的数,那么：
q[l][r]=max(f[l][j],f[r-2j+1][j]);
编程时，注意1<<i=2^i
例题 luogu1816
题解
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
int f[100010][100];
int a[100010];
int n,q,x,y;
void rmq_init()
{
for (int i=1;i<=n;i++)
f[i][0]=a[i];
int i=1,j=1;
for (int j=1;(1<<j)<n;j++)
for (int i=1;i+(1<<j)<=n;i++)
f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
int rmq_query(int l,int r)
{
int pos;
for (pos=0;(1<<pos)<=(r-l+1);pos++);
pos--;
return (min(f[l][pos],f[r-(1<<pos)+1][pos]));
}
main()
{
memset(f,0x7f,sizeof f);
scanf("%d%d",&n,&q);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
rmq_init();
for (int i=1;i<=q;i++)
{
scanf("%d%d",&x,&y);
printf("%d ",rmq_query(x,y));
}
}
好了，回归我们的LCA问题
LCA 问题可以转化为 RMQ 问题求解，方法为：
观察：节点u与v的LCA正是对树T进行深度优先遍历过程中u节点与v节点之间的具有最浅深度的节点，下图展示了对一颗树的深度优先遍历过程，以及形成的欧拉迹。
注：设树节点数为n，则欧拉迹的大小为2n-1
对于一颗树T，我们创建三个数组： E [1,..,2n-1]，存放树T的欧拉迹，E[i]表示欧拉迹中第i个节点的标号；L [1,..2n-1]，存放欧拉迹中各节点的深度，根节点深度为0； R [1,..n]，R[i]存放第i个节点在欧拉迹中第一次出现的位置。例如：
为了计算LCAT(x,y):
欧拉迹中处于x和y之间的所在节点为ER[x],..,R[y]。在这个子迹中，最浅节点的标号为RMQL(R[x],R[y])，这里RMQ算法查找最小节点的标号。此时LCAT(x,y)= RMQL(R[x],R[y])
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define M 500000*2+10
#define N 500000*2+10
using namespace std;
struct node
{
int to,next;
}e[M];
int tot,st[M];
int n,m,root,x,y;
int f[N][20];
int dfs_list[N],depth[N],first[N];
void add(int x,int y)
{
e[++tot].to=y;
e[tot].next=st[x];
st[x]=tot;
}
int pow_2(int j)
{
return (1<<j);
}
void rmq_init()
{
for (int i=1;i<=2*n-1;i++)
f[i][0]=i;
int i=1,j=1;
for (int j=1;pow_2(j)<=2*n-1;j++)
for (int i=1;i+pow_2(j)<=2*n-1;i++)
{
int a=depth[f[i][j-1]];
int b=depth[f[i+pow_2((j-1))][j-1]];
if (a<b)
f[i][j]=f[i][j-1];
else
f[i][j]=f[i+pow_2((j-1))][j-1];
}
}
int rmq_query(int l,int r)
{
int pos;
for (pos=0;pow_2(pos)<(r-l+1);pos++);
pos--;
int a=depth[f[l][pos]];
int b=depth[f[r-pow_2(pos)+1][pos]];
if (a<b)
return dfs_list[f[l][pos]];
else
return dfs_list[f[r-(1<<pos)+1][pos]];
}
int dfs_clock=0;
void dfs(int now,int pre,int deep)
{
dfs_list[++dfs_clock]=now;
depth[dfs_clock]=deep;
if (!first[now])
first[now]=dfs_clock;
for (int i=st[now];i;i=e[i].next)
if (e[i].to!=pre)
{
dfs(e[i].to,now,deep+1);
dfs_list[++dfs_clock]=now;
depth[dfs_clock]=deep;
}
}
main()
{
scanf("%d%d%d",&n,&m,&root);
for (int i=1;i<n;i++)
scanf("%d%d",&x,&y),add(x,y),add(y,x);
dfs(root,-1,0);
rmq_init();
for (int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
if (first[x]>first[y]) swap(x,y);
//printf("%d %d\n",first[x],first[y]);
printf("%d\n",rmq_query(first[x],first[y]));
}
}