代码针对洛谷P3379
1.向上标记法
最朴素的求最近公共祖先的方法，两个子结点同时向上一个一个的跳，标记已经跳过的点，如果有一个点跳到了已经标记过的点，那么就说明这个点就是最近公共祖先。可以自己简单的推一下，查询的时间复杂度为 $ O(n) $ 。
2.倍增
总思路：用类似于二进制拆分的思想。
首先我们先理清楚二进制数的特点，对于一个数$2^n$，我们可以用$2^0,2^1…2^n-1$，来表示出任何一个小于$2^n$的数。
举例：
$8=1000\,=2^3$
$7=0111\,=2^2+2^1+2^0$
$6=0110\,=2^2+2^1$
$5=0101\,=2^2+2^0$
$4=0100\,=2^2$
$3=0011\,=2^1+2^0$
$2=0010\,=2^1$
$1=0001\,=2^0$
下面来介绍一下算法的思路，来解释一下为什么与二进制数的拆分有关系。
算法思路：
当x与y在不同深度时，最近公共祖先肯定不会是深度大的那个结点，所以说，我们可以将x与y调整到同一深度，将深度大的点不断往上跳，直到两个点深度相同。这与求两个点的最近公共祖先是等效的。
那么要怎么样让结点小的点往上跳呢，首先，我们要进行一遍处理，预处理出每个节点的第$2^k$的父结点。这样子在往上跳的时候，就可以直接跳到2的k次方。
那么我们首先将深度大的点不断向上跳，直到两个点深度相同。（具体可以看代码，这里就要用到二进制拆分了。）
这里如果要推的话有个推理，当求两个点（如x和y）的最近公共祖先时，如果x或y不是最近公共祖先那么求x和y的最近公共祖先等效于求x的父结点和y的父结点的最近公共祖先。
因此我们可以推出，当x与y的$2^k$祖先不是最近公共祖先时，我们可以直接将问题改为求x的$2^k$的父结点和y的$2^k$的父结点的最近公共祖先。
那么当x和y的$2^k$的祖先相同时，我们就不往上跳，当x与y的$2^k$的祖先不同时，我们就向上跳$2^k$，最后可以保证跳完后x的祖先或y的祖先即为x和y的最近公共祖先。
而上面讲述二进制拆分就是为了讲述如何保证不跳少了。
比如说如果x和y的最近公共祖先是x的第7个父结点时，刚开始从$2^k$，一支循环到$2^3$，发现x的第8个父结点与y的第8个父结点是相同的，所以不往上跳，而剩下的$2^2$发现父结点不同，向上跳4，$2^1$，发现父结点不同，向上跳2，最后发现父结点相同了不在往上跳。那么此时x以及y的父结点就是要求的最近公共祖先。
代码：
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#define NN N<<1
using namespace std;
const int N=5e5+10;
int n,m,s,t,a,b,d[N],f[N][200],e[NN],ne[NN],h[N],cnt;
queue<int> q;
void add(int a,int b){
e[++cnt]=b;
ne[cnt]=h[a];
h[a]=cnt;
}
void bfs(int s){
q.push(s);d[s]=1;
while(q.size()){
int x=q.front();q.pop();
for(int i=h[x];i;i=ne[i]){
int y=e[i];
if(d[y])continue;
d[y]=d[x]+1;
f[y][0]=x;
for(int i=1;i<=t;i++){
f[y][i]=f[f[y][i-1]][i-1];
}
q.push(y);
}
}
}
int lca(int x,int y){
if(d[x]>d[y]) swap(x,y);
for(int i=t;i>=0;i--){
if(d[f[y][i]]>=d[x]) y=f[y][i];
}
if(x==y) return x;
for(int i=t;i>=0;i--){
if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
}
return f[x][0];
}
int main(){
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<n;i++){
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
t=(int)(log(n)/log(2))+1;
bfs(s);
for(int i=1;i<=m;i++){
scanf("%d%d",&a,&b);
printf("%d\n",lca(a,b));
}
}
3.树链剖分
树链剖分有很多种，这里讲的是重链剖分，简单的来说是对于每个结点来说，将他的子儿子中子树的节点数最多的子儿子作为重儿子（等图片上来后更清楚）。
重链剖分：用子节点个数来确定重儿子和轻儿子，且将连续的重儿子连成一条链，使得树被分为多条链。
实现：
两次dfs，第一次，找出重儿子，深度，父节点。第二次dfs，确定点的dfn序和rnk序，以及每个点的重顶点。
查询：
若在同一条重链上，则深度小的点为最近公共祖先。若不在，则将重顶点的深度大的点通过跳到链顶的方式，直到两个点到同一条重链上。
证明：
这里是我的不严谨证明：
若两个节点不在同一条重链上，则最近公共祖先（下面以lca代替）不可能在链顶深度大的重链中，此时，求x与y的lca与x与top[y]的lca相同，同理x与f[top[y]]的lca相同，以此直到在同一条重链中。
代码：
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stdio.h>
#define NN N<<1
using namespace std;
const int N=5e5+10;
int n,m,s,h[N],e[NN],ne[NN],son[N],top[N],siz[N],f[N],dep[N];
int a,b,cnt;
void add(int a,int b){
e[++cnt]=b;
ne[cnt]=h[a];
h[a]=cnt;
}
void dfs1(int x){
son[x]=-1;
siz[x]=1;
for(int i=h[x];i;i=ne[i]){
int ver=e[i];
if(ver!=f[x]){
if(!dep[ver]){
dep[ver]=dep[x]+1;
f[ver]=x;
dfs1(ver);
siz[x]+=siz[ver];
if(siz[son[x]]<siz[ver]) son[x]=ver;
}
}
}
}
void dfs2(int x,int t){
top[x]=t;
if(son[x]==-1) return;
dfs2(son[x],t);
for(int i=h[x];i;i=ne[i]){
int ver=e[i];
if(ver!=son[x]&&ver!=f[x])dfs2(ver,ver);
}
}
int lca(int a,int b){
while(top[a]!=top[b]){
if(dep[top[a]]>dep[top[b]]) a=f[top[a]];
else b=f[top[b]];
}
return dep[a]<dep[b]?a:b;
}
int main(){
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<n;i++){
scanf("%d%d",&a,&b);
add(a,b);add(b,a);
}
dfs1(s);dfs2(s,s);
for(int i=1;i<=m;i++){
scanf("%d%d",&a,&b);
printf("%d\n",lca(a,b));
}
}4.Tarjan
还不会
