LCA的裸题。LCA可以用三种方式求解，其中离线算法有Tarjan，在线算法有倍增，RMQ，个人觉得RMQ效率会高一点。
有个博客讲解的很好，链接：
https://blog.csdn.net/my_sunshine26/article/details/72717112
这里我总结了一下三种方法的关键点：
1.Tarjan求LCA
核心：离线+DFS后序遍历+并查集
1.开设vis[i], fa[i]，分别记录i节点是否被访问过，i节点的父节点；
2.从根节点开始搜索，DFS后序遍历；
3.当当前节点u没有子节点时，即开始访问u节点，vis[u]=1，fa[u]=pre，查询是否有询问u与其他节点的关系，没有询问或者询问的节点v尚未访问，就退回上一层DFS，否则，用并查集的find()函数找出<u,v>之间的LCA（find()函数是找到包含u,v节点的最小子树的根，根据LCA的性质我们可以知道该子树的根即为<u,v>的LCA）。
4.重复上述操作，直到整棵树遍历完。
2.倍增法求LCA
前期铺垫：
[1].depth[i]为i到根节点的深度，如果w是u,v的LCA，那么u往上走depth[u]-depth[w]步，v往上走depth[v]-depth[w]步，它们都会到达w，那么假设depth[u]>=depth[v]，我们可以先让u往上走depth[u]-depth[v]步，再让u,v同时一步一步往上走，第一次到达的公共点就是它们的LCA了。
[2].如果w是u,v的LCA，那么从w往上走，经过的任意一点都是u,v的公共祖先。
因为我们让u先往上走，再让u,v同时往上走，都是一步一步的去进行的，时间开销稍微大了点，所以倍增算法优化的就是这个往上走的过程，原本是一步一步走，可以优化成走1,2,4,8,…步。
核心：设置fa[i][j]，表示第i个节点往上走2^j次步到达的节点，显然fa[i][j]=fa[fa[i][j-1][j-1]，预处理出fa[i][j]数组，这个算法基本上就完成一大部分了。
3.RMQ求解LCA
核心：DFS序转化+RMQ
该算法要熟记每个数组代表的意义以及DFS序的性质，理解好后，这个算法也就差不多可以理解了。
[1].设置id[i]，表示第i次DFS遍历的节点的编号；
[2].设置depth[i]，表示第i次DFS遍历的节点的编号在树中的深度；
[3].设置in[i]，表示节点i在DFS序（即id[]数组）中第一次出现的位置；
[4].设置dp[i][j]，用以查询区间[i,i+2j-1]里深度最小的编号(DFS序编号）
对于本题，我只写了倍增和RMQ的AC代码。
倍增法：
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<algorithm>
#include<stack>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn=1e4+5;
int head[maxn],cnt;
int depth[maxn],fa[maxn][15];
struct Edge
{
int v,next;
}e[2*maxn];
void addedge(int u,int v)
{
e[cnt].v=v;
e[cnt].next=head[u];
head[u]=cnt++;
e[cnt].v=u;
e[cnt].next=head[v];
head[v]=cnt++;
}
void DFS(int u,int pre,int d)
{
fa[u][0]=pre;
depth[u]=d;
for(int i=head[u]; i ;i=e[i].next)
{
if(e[i].v!=pre)
DFS(e[i].v,u,d+1);
}
}
void init(int root,int n)
{
DFS(root,-1,1);
for(int j=1;(1<<j)<n;++j)
for(int i=1;i<=n;++i)
{
if(fa[i][j-1]==-1) fa[i][j]=-1;
else fa[i][j]=fa[fa[i][j-1]][j-1];
}
}
int LCA(int u,int v,int n)
{
if(depth[v]>depth[u]) swap(u,v);
int temp=depth[u]-depth[v];
for(int i=0;(1<<i)<=temp;++i)
if((1<<i)&temp)
u=fa[u][i];
if(u==v) return u;
int k=0;
while((1<<(k+1))<=n) ++k;
for(int i=k;i>=0;--i)
{
if(fa[u][i]!=fa[v][i])
{
u=fa[u][i];
v=fa[v][i];
}
}
return fa[u][0];
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,root;
scanf("%d",&n);
memset(head,0,sizeof(head)); cnt=2;
for(int i=1;i<=n-1;++i)
{
int a,b;
scanf("%d%d",&a,&b);
if(i==1) root=a;
addedge(a,b);
}
int x,y;
scanf("%d%d",&x,&y);
init(root,n);
printf("%d\n",LCA(x,y,n));
}
return 0;
}
RMQ法：
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<algorithm>
#include<stack>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn=1e4+5;
int head[maxn],cnt;
int depth[2*maxn],id[2*maxn],in[maxn],num;
int dp[2*maxn][15];
struct Edge
{
int v,next;
}e[2*maxn];
void addedge(int u,int v)
{
e[cnt].v=v;
e[cnt].next=head[u];
head[u]=cnt++;
e[cnt].v=u;
e[cnt].next=head[v];
head[v]=cnt++;
}
void DFS(int u,int pre,int d)
{
id[++num]=u;
in[u]=num;
depth[num]=d;
for(int i=head[u]; i ;i=e[i].next)
{
if(e[i].v!=pre)
{
DFS(e[i].v,u,d+1);
id[++num]=u;
depth[num]=d;
}
}
}
void init(int n)
{
for(int i=1;i<=n;++i) dp[i][0]=i;
for(int j=1;(1<<j)<=n;++j)
for(int i=1;i+(1<<j)-1<=n;++i)
{
int a=dp[i][j-1], b=dp[i+(1<<(j-1))][j-1];
if(depth[a]<depth[b]) dp[i][j]=a;
else dp[i][j]=b;
}
}
int RMQ(int l,int r)
{
int k=0;
while((1<<(k+1))<=r-l+1) ++k;
int a=dp[l][k], b=dp[r-(1<<k)+1][k];
return depth[a]<depth[b]? a:b;
}
int LCA(int u,int v)
{
int l,r;
l=in[u]; r=in[v];
if(l>r) swap(l,r);
return id[RMQ(l,r)];
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,root;
scanf("%d",&n);
memset(head,0,sizeof(head)); cnt=2; num=0;
for(int i=1;i<=n-1;++i)
{
int a,b;
scanf("%d%d",&a,&b);
if(i==1) root=a;
addedge(a,b);
}
int x,y;
scanf("%d%d",&x,&y);
DFS(root,-1,1);
init(2*n);
printf("%d\n",LCA(x,y));
}
return 0;
}
![树的基本概念(定义、基本术语、性质)[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)