LCA（最近公共祖先）

LCA(Lowest Common Ancesto) 就是今天的主角，又叫最近公共祖先，用来求两个节点的最小父节点。

1.简介

LCA算法是一种倍增算法，分为3个步骤：遍历深度与父节点、倍增初始化和LCA主函数。

2.代码

1.遍历深度与父节点（附main函数调用方式）

int n, m, s, f[100005][33],dep[100005];//倍增数组和深度数组
vector<int> a[500005];//结点vector

void dfs(int u, int fa){
	f[u][0] = fa;
    dep[u] = dep[fa]+1;
    
    for (int i = 0; i < a[u].size(); i++){
    	if (fa != a[u][i]) dfs(a[u][i], u);
    }
}

//主函数
dfs(0, 0);

2.倍增初始化

void init(){
	for (int j = 1; (1 << j) <= n; j++){
    	for (int i = 1; i <= n; i++) f[i][j] = f[f[i][j-1]][j-1];
    }
}

3.LCA主函数

int LCA(int u, int v){
	if (dep[u] < dep[v]) swap(u, v);
    
    for (int i = 22; i >= 0; i--){
    	if (dep[f[u][i]] >= dep[v]) u = f[u][i];
    }
 	
    if (u == v) return u;
    
    for (int i = 22; i >= 0; i--){
    	if (f[u][i] != f[v][i]){
        	u = f[u][i];
            v = f[v][i];
        }
    }
    
    return f[u][0];
}

这就是LCA的全部了，点个赞再走呗。