代码针对洛谷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

还不会