我目前学会的两种求LCA的算法：
A、Tarjan算法（离线算法）
算法思路：
1、从根结点开始dfs。
2、遍历点x的所有子节点。
3、从某一个子节点y返回x时，要在并查集中把x,y所在的两棵子树合并，且根节点为点x所在子树的根节点。
4、离开结点x前，要看看是否有与x相关的询问(x,y),如果有且结点y已被访问过，(x,y)的LCA就是并查集中点y所在子树的根节点。
注意各个步骤实现的顺序：递归 - > 合并 - > 查找询问 - > 返回
代码：
#include<cstdio>
#include<iostream>
#include<vector>
using namespace std;int n;
vector<int> a[10005];
int ask1,ask2;
bool use1,use2;int fa[10005]= {0};
int find(int x) {if(fa[x]==0) {return x;}return fa[x]=find(fa[x]);
}bool flag=false;
void lca(int x) {if(x==ask1) use1=true;if(x==ask2) use2=true;for(int i=0; i<a[x].size(); i++) {lca(a[x][i]);fa[a[x][i]]=x;}if(x==ask1&&use2==true&&flag==false) {printf("%d\n",find(ask2));flag=true;} else if(x==ask2&&use1==true&&flag==false) {printf("%d\n",find(ask1));flag=true;}return ;
}int main() {int t;scanf("%d",&t);while(t--) {bool root[10005]={0};scanf("%d",&n);use1=use2=false;flag=false;for(int i=1; i<=n; i++) {a[i].clear();root[i]=true;fa[i]=0;}for(int i=1; i<=n-1; i++) {int x,y;scanf("%d%d",&x,&y);a[x].push_back(y);root[y]=false;}scanf("%d%d",&ask1,&ask2);for(int i=1;i<=n;i++){if(root[i]==true){lca(i);}}}return 0;
}------------------------------------------------------------------------------------------------------------------------------------------------------------
B、倍增法（在线算法）
算法思路：
1、进行一次dfs，初始化出每一个节点x的深度deep[x]以及上2^i层的祖先anc[x][i]。
2、调整询问的x（deep[x]>deep[y]）结点高度，让x、y结点在同一高度。
3、同时倍增x、y两结点，求出LCA。
倍增时，i从大到小循环，每当anc[x][i]!=anc[y][i]时，就说明最近公共祖先在x,y的上2^i层与上2^(i+1)层之间，就将x，y变为anc[x][i]，anc[y][i]，再次重复刚刚的步骤（类似二分搜索）。
代码：
#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;int n;
vector<int> a[10005];int anc[10005][20]= {0};
int deep[10005]= {0};
void dfs(int x,int fa) {anc[x][0]=fa;for(int i=1; i<=15; i++) {anc[x][i]=anc[anc[x][i-1]][i-1];}for(int i=0; i<a[x].size(); i++) {deep[a[x][i]]=deep[x]+1;dfs(a[x][i],x);}return ;
}int LCA(int x,int y) {if(deep[x]<deep[y]) swap(x,y);for(int i=15; i>=0; i--) {if (deep[y]<=deep[anc[x][i]]) {x=anc[x][i];}}if(x==y) return x;for(int i=15; i>=0; i--) {if(anc[x][i]!=anc[y][i]) {x=anc[x][i],y=anc[y][i];}}return anc[x][0];
}int main() {int t;scanf("%d",&t);while(t--) {bool root[10005]= {0};memset(root,true,sizeof(root));scanf("%d",&n);for(int i=1; i<=n; i++) {a[i].clear();}memset(anc,0,sizeof(anc));memset(deep,0,sizeof(deep));deep[0]=-1;for(int i=1; i<=n-1; i++) {int x,y;scanf("%d%d",&x,&y);a[x].push_back(y);root[y]=false;}for(int i=1; i<=n; i++) {if(root[i]==true) {dfs(i,0);break;}}int ask1,ask2;scanf("%d%d",&ask1,&ask2);printf("%d\n",LCA(ask1,ask2));}return 0;
}