题目描述
求树中两个点的最近公共祖先
算法1
(倍增求LCA) $O(\log_2{N})$
预处理:depth数组和fa[][]数组
void dfs(int u,int father)
{
depth[u] = depth[father] + 1;
fa[u][0] = father;
for(int i = 1;i <= 18;i++)
fa[u][i] = fa[fa[u][i-1]][i-1];
for(int i = h[u];~i;i=ne[i])
{
int j = e[i];
if(j == father)continue;
dfs(j,u);
}
}
1.先让a(更深的点)跳到与b同一层
for(int i = 18;i >= 0;i--)
{
if(depth[fa[a][i]] >= depth[b])//跳了2的n次方,a的深度仍然在b同水平或以下
a = fa[a][i];//a就跳
}
//如果两者深度之差为11 ,(1011)二进制
//i == 4的时候满足条件,如果在i > 4的时候跳,a的深度会比b小
//当i == 1的时候,深度之差为1,a向上跳一个,满足条件,跳
a和b一起跳,跳到最近祖先节点的下一层
for(int i = 18;i >= 0;i--)
{
if(fa[a][i] != fa[b][i])
a = fa[a][i] , b = fa[b][i];
}
//要跳到最近公共祖先的下一行
//如果跳8层,2的三次方恰好到达
//那么就不会再跳了