两个最近的点u和v的最近的公共的祖先称为最近公共祖先(LCA)。普通的LCA算法，每算一次LCA的时间复杂度为线性o(n);
这里讲LCA + 二分的方法。首先对于任意的节点v，利用其父节点的信息，可以通过par2[v]=par[par[v]]得到向上走两步的节点。依此信息可以通过par4[v]=par2[par2[v]]得到向上走4步的节点。所以，根据此方法可以得到向上走2^k所得到的节点par[k][v]。每次搜索的复杂度为o(log n)，预处理par[k][v]的复杂度为o(nlog n)。(我觉得挑战程序设计LCA部分写的挺明白的)
模版代码如下:
//LCA + 二分 vector <int> G[MAX_V]; //邻接表
int root; //根的编号 int par[MAX_LOG_V][MAX_V]; // 向上走2^k所到的父节点编号(根节点的父节点为-1)
int dep[MAX_V]; //节点的深度 void dfs(int v , int p , int d) { //3个参数分别表示 当前节点 父节点 深度
par[v][] = p;
dep[v] = d;
for(int i = ; i < G[v].size() ; i++) {
dfs(G[v][i] , v , d + );
}
}
//预处理
void init(int n) {
dfs(root , - , ); //预处理出par[0]和dep
for(int k = ; k + < MAX_LOG_V ; k++) {
for(int v = ; v <= n ; v++) {
if(par[k][v] < )
par[k + ][v] = -; //v向上的2 ^ (k + 1)的节点超过根节点
else
par[k + ][v] = par[k][par[k][v]]; //v向上的2^k的节点 又向上的2^k个节点，所以是向上2^(k + 1)个节点
}
}
}
//计算u和v的LCA
int lca(int u , int v) {
if(dep[u] < dep[v]) //让u和v向上走到同一深度
swap(u , v);
for(int k = ; k < MAX_LOG_V ; k++) {
if((dep[v] - dep[u]) >> k & ) { //把深度差化为2进制(快速幂原理) 依次从低位相减
v = par[k][v];
}
}
if(u == v) //要是节点相同则输出LCA
return u;
for(int k = MAX_LOG_V - ; k >= ; k--) { //二分搜索计算LCA
if(par[k][u] != par[k][v]) { //若他们的2^k节点不相同 则u和v向上移动，一直移动直到他们的上一个节点相同
u = par[k][u];
v = par[k][v];
}
}
return par[][u];
}