LCA问题:给定一颗 个结点的有根树,有 次询问,每次询问给出结点 ,求 的最近公共祖先。此类问题通称 LCA 。 暴力 一次一次把 向上提,知道 与 相等为止。 倍增加速 在上面暴力的思想中,是一步一步向上跳的。 倍增的核心思想就是 步 步向上跳。 我们需要先处理出第 个点的第 个祖先。 如何求出? 设 为第 个点向上跳 后所处的位置,根据初一学习的幂的性质,我们认为第 个点向上跳 后所处的位置就是第 个点向上跳 后再向上跳 ()。 所以我们有: 可以递推出来: void dfs(int u, int fa) //当前是第 u 个结点,u 的父亲是 f...