8.29 倍增进阶+树上LCA

· · 算法·理论

LCA 最近公共祖先

定义：

两个节点的最近公共祖先，就是这两个点的公共祖先里面，离根最远的那个

性质：

  3. 如果 u 不为 v 的祖先并且 v 不为 u 的祖先，那么 u,v 分别处于 \text{LCA}(u,v) 的两棵不同子树中；

  4. 前序遍历中，\text{LCA}(S) 出现在所有 S 中元素之前，后序遍历中 \text{LCA}(S) 则出现在所有 S 中元素之后；

  5. 两点集并的最近公共祖先为两点集分别的最近公共祖先的最近公共祖先，即 \text{LCA}(A\cup B)=\text{LCA}(\text{LCA}(A), \text{LCA}(B))；

  6. 两点的最近公共祖先必定处在树上两点间的最短路上；

  7. $d$ 是树上两点间的距离，$h$ 代表某点到树根的距离;

求LCA

若求 (x,y) 的 LCA ：

倍增

先预处理出一个 st\text{表 } dp_{i,j} dp_{i,j} 表示第 i 个点走 2^{j-1}个单位到达的位置，还要预处理出每个点的深度 dep_i 表示第 i 点的深度

void dfs(int u,int f){
    dp[u][0]=f;
    dep[u]=dep[f]+1;
    for(int j(1);j<=20;j++){
        dp[u][j]=dp[dp[u][j-1]][j-1];
    }
    for(int i(0);i<e[u].size();i++){
        if(f==e[u][i]){
            continue;
        }
        dep[e[u][i]]=dep[u]+1;
        dfs(e[u][i],u);
    }
    return;
}

再将 x \text{ 和 } y 中深度较深的一个向上跳，直到他们深度相等：

注意到如果当他们深度一致且在同一点时就直接返回

if(dep[x]<dep[y]){  //假设x的深度一定比y深，如果小了就交换
    swap(x,y);
}
for(int i(20);i>=0;i--){
  if(dep[dp[x][i]]>=dep[y]){
      x=dp[x][i];
  }
}
if(x==y){  //深度一致且在同一点时就直接返回
    return y;
}

在两点高度都相等后，我们使两个点同时向上跳，直到跳到他们的 LCA 的下两个点，最后输出还要向上跳一步

for(int i(20);i>=0;i--){
    if(dp[x][i]!=dp[y][i]){
        x=dp[x][i];
        y=dp[y][i];
    }
}
return dp[x][0];  //记得最后是停留在LCA的下面，所以在返回前还要向上跳一步