LAC树上最近公共祖先详解

root 大佬 LV 3 SU · 2026-9-4 19:27:43

当然。这里的 LCA（Lowest Common Ancestor，最近公共祖先） 是树上非常经典的算法，也是算法竞赛里必须掌握的内容。

我按「是什么 → 怎么想 → 倍增做法 → 代码 → 手算 → 复杂度 → 常见坑」给你讲。

1. LCA 是什么？

给一棵树，任意两个节点 u、v：

LCA(u, v) = u 和 v 的所有公共祖先中，距离它们最近的那个。

例如：

              1
            /   \
           2     3
         /  \   / \
        4    5 6   7
            / \
           8   9

比如：

LCA(4, 5) = 2
LCA(4, 8) = 2
LCA(8, 9) = 5
LCA(4, 6) = 1
LCA(8, 3) = 1

2. 为什么需要 LCA？

假设有：

1
├── 2
│   ├── 4
│   └── 5
└── 3
    ├── 6
    └── 7

现在问：

4 到 7 的路径经过哪些点？

实际上：

4 → 2 → 1 → 3 → 7

中间那个关键点就是：

LCA(4,7) = 1

所以 LCA 经常用来解决：

树上两点距离
树上路径问题
树上最近公共节点
树上路径修改/查询
树上差分
倍增
树链剖分

3. 最简单的思路

假设：

求：

LCA(4, 5)

我们知道：

4 的祖先：

4 → 3 → 2 → 1

5 的祖先：

5 → 3 → 2 → 1

第一个共同出现的就是：

所以：

LCA(4,5)=3

4. 最暴力的方法

我们可以：

从 u 一直往上走，把所有祖先标记。
从 v 一直往上走。
第一个遇到的标记节点就是 LCA。

例如：

u = 8

8 → 5 → 2 → 1

标记：

8 5 2 1

然后：

v = 9

9 → 5

发现 5 已经被标记：

LCA(8,9)=5

但是最坏情况下：

1
|
2
|
3
|
4
|
...
|
n

一次查询可能需要 O(n)。

如果：

n = 10^5
q = 10^5

就可能达到：

O(nq) = 10^10

肯定不行。

5. LCA 的核心：倍增

这就是竞赛中最经典的 LCA 方法。

核心思想特别简单：

不要让节点一个一个往上跳，而是让它一次跳 1、2、4、8、16……层。

6. `fa[u][j]` 是什么？

定义：

fa[u][j]

表示：

节点 u 向上跳 2^j 层之后到达的节点。

例如：

fa[u][0]

就是：

u 的父亲

因为：

2^0 = 1

fa[u][1]：

向上跳 2 层

fa[u][2]：

向上跳 4 层

fa[u][3]：

向上跳 8 层

所以：

j       跳跃距离
----------------
0          1
1          2
2          4
3          8
4         16
5         32
...

7. 倍增数组怎么计算？

这是 LCA 最重要的公式：

fa[u][j] = fa[ fa[u][j-1] ][j-1];

为什么？

因为：

向上跳 2^j

=

先向上跳 2^(j-1)

再向上跳 2^(j-1)

例如：

2^3 = 8

8 = 4 + 4

所以：

fa[u][3]

就是：

先跳4层
再跳4层

也就是：

fa[ fa[u][2] ][2]

8. DFS 预处理

首先我们需要知道每个节点：

depth[u]

表示深度。

以及：

fa[u][j]

表示第 2^j 个祖先。

例如：

          1       depth=0
        /   \
       2     3    depth=1
      / \
     4   5        depth=2

那么：

depth[1] = 0
depth[2] = 1
depth[3] = 1
depth[4] = 2
depth[5] = 2

同时：

fa[4][0] = 2
fa[4][1] = 1
fa[4][2] = 0

9. C++ 标准模板

这是最应该记住的一版：

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
const int LOG = 20;

vector<int> g[N];

int fa[N][LOG];
int depth[N];

void dfs(int u, int father)
{
    fa[u][0] = father;
    depth[u] = depth[father] + 1;

    for (int i = 1; i < LOG; i++)
    {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }

    for (int v : g[u])
    {
        if (v == father)
            continue;

        dfs(v, u);
    }
}

这里最重要的是：

fa[u][0] = father;

以及：

fa[u][i] = fa[fa[u][i - 1]][i - 1];

10. 查询 LCA

现在我们已经有了：

depth[]
fa[][]

那么：

LCA(u,v)

分三步。

第一步：让两个节点处于同一深度

例如：

现在：

u = 5
v = 3

显然：

LCA(5,3)=3

但：

depth[5] = 4
depth[3] = 2

所以我们先把 5 往上跳：

5 → 3

11. 怎么快速跳？

假设：

depth[u] - depth[v] = 13

13 可以拆成：

13 = 8 + 4 + 1

也就是：

2^3 + 2^2 + 2^0

所以：

for (int i = 0; i < LOG; i++)
{
    if (diff & (1 << i))
        u = fa[u][i];
}

例如：

diff = 13

二进制：

1101

对应：

8 + 4 + 1

所以：

u
↓ 8
↓ 4
↓ 1

总共跳 13 层。

12. 第二步：如果已经相同

假设调整后：

u == v

那么直接：

return u;

为什么？

因为如果一个节点是另一个节点的祖先：

求：

LCA(2,3)

答案就是：

13. 第三步：一起往上跳

这是整个 LCA 最精髓的地方。

假设：

              1
            /   \
           2     3
          /       \
         4         6
        /           \
       8             7

求：

LCA(8,7)

现在：

u = 8
v = 7

如果我们直接往上：

8 → 4 → 2 → 1
7 → 6 → 3 → 1

但是我们不知道什么时候该停。

所以采用：

从最大的跳跃开始，只要跳完之后两个人还不是同一个节点，就一起跳。

14. 为什么是“还不是同一个节点”？

假设：

u
 \
  ...
   \
    LCA

如果：

fa[u][i] != fa[v][i]

说明：

两个人向上跳 2^i 层之后，仍然处于 LCA 的两侧。

所以：

u = fa[u][i];
v = fa[v][i];

放心跳。

如果：

fa[u][i] == fa[v][i]

说明：

再跳这么远，就会直接跳到公共祖先甚至越过关键位置。

所以：

不能跳。

最后：

u 和 v

会停在：

LCA 的两个儿子

那么：

return fa[u][0];

就是答案。

15. 完整 LCA 函数

int lca(int u, int v)
{
    // 1. 保证 u 比 v 深
    if (depth[u] < depth[v])
        swap(u, v);

    // 2. 让 u、v 深度相同
    int diff = depth[u] - depth[v];

    for (int i = 0; i < LOG; i++)
    {
        if (diff & (1 << i))
            u = fa[u][i];
    }

    // 3. 如果 u 已经是 v 的祖先
    if (u == v)
        return u;

    // 4. 从大到小尝试跳
    for (int i = LOG - 1; i >= 0; i--)
    {
        if (fa[u][i] != fa[v][i])
        {
            u = fa[u][i];
            v = fa[v][i];
        }
    }

    // 5. 此时 u、v 是 LCA 的两个儿子
    return fa[u][0];
}

这个模板非常重要。

16. 用一个具体例子跑一遍

还是：

              1
            /   \
           2     3
         /  \   / \
        4    5 6   7
            / \
           8   9

求：

LCA(8,7)

第一步：深度

depth[8] = 3
depth[7] = 2

所以：

8 比 7 深 1 层

把 8 往上跳：

8 → 5

现在：

u = 5
v = 7

第二步：从大到小跳

尝试：

2^2 = 4

看：

fa[5][2]
fa[7][2]

显然已经超过树的高度，通常会指向 0，所以不能跳。

再试：

2^1 = 2

假设：

fa[5][1] = 1
fa[7][1] = 1

相同。

不能跳。

再试：

2^0 = 1

：

fa[5][0] = 2
fa[7][0] = 3

不相同。

所以：

5 → 2
7 → 3

现在：

u = 2
v = 3

它们的父亲都是：

所以：

return fa[2][0];

得到：

因此：

LCA(8,7)=1

17. 为什么时间复杂度是 O(log n)？

假设：

n = 100000

那么：

log₂(100000) ≈ 17

我们只需要保存：

0 ~ 17

这些倍增信息。

也就是：

一次查询最多遍历这些层数：

O(log n)

18. 完整代码

可以直接用于大部分竞赛题：

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
const int LOG = 20;

vector<int> g[N];

int fa[N][LOG];
int depth[N];

void dfs(int u, int father)
{
    fa[u][0] = father;
    depth[u] = depth[father] + 1;

    for (int i = 1; i < LOG; i++)
    {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }

    for (int v : g[u])
    {
        if (v == father)
            continue;

        dfs(v, u);
    }
}

int lca(int u, int v)
{
    // 保证 u 更深
    if (depth[u] < depth[v])
        swap(u, v);

    // 拉到同一深度
    int diff = depth[u] - depth[v];

    for (int i = 0; i < LOG; i++)
    {
        if (diff & (1 << i))
            u = fa[u][i];
    }

    // 如果一个是另一个的祖先
    if (u == v)
        return u;

    // 从大到小跳
    for (int i = LOG - 1; i >= 0; i--)
    {
        if (fa[u][i] != fa[v][i])
        {
            u = fa[u][i];
            v = fa[v][i];
        }
    }

    return fa[u][0];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;

        g[u].push_back(v);
        g[v].push_back(u);
    }

    // 假设 1 是根
    dfs(1, 0);

    while (q--)
    {
        int u, v;
        cin >> u >> v;

        cout << lca(u, v) << '\n';
    }

    return 0;
}

19. LCA 最应该记住的 4 个东西

如果你是准备算法竞赛，实际上先把下面四个东西吃透就够了：

① `depth`

depth[u]

表示节点深度。

② `fa[u][0]`

fa[u][0] = father;

表示父节点。

③ 倍增公式

fa[u][i] = fa[fa[u][i-1]][i-1];

这是核心。

④ LCA 查询

// 先把深的拉上来
// 再从大到小一起跳
// 最后父亲就是 LCA

可以把它记成一句话：

先齐平，再一起跳；能跳就跳，不能跳就不跳。

20. LCA 和树上距离

LCA 非常常见的一个应用就是：

求树上两个节点之间的距离。

公式：

dist(u,v)
=
depth[u] + depth[v] - 2 × depth[LCA(u,v)]

例如：

求：

4 → 5

有：

depth[4] = 2
depth[5] = 2
LCA(4,5) = 1

所以：

dist(4,5)
= 2 + 2 - 2×1
= 2

路径就是：

4 → 2 → 1 → 3 → 5

等等，这里要注意深度计算：如果根 1 深度为 1，则：

depth[4] = 3
depth[5] = 3
depth[1] = 1

距离：

3 + 3 - 2×1 = 4

正好：

4 → 2 → 1 → 3 → 5

4 条边。

所以竞赛里深度从 0 还是 1 开始都可以，关键是保持一致。

21. 倍增 LCA 的整体思维

你可以把整个算法想象成：

首先：

① 深度不同
       ↓
   把深的拉上来
       ↓
② 深度相同
       ↓
   从最大步长开始
       ↓
③ 如果两人跳过去仍不同
       ↓
      一起跳
       ↓
④ 最终停在 LCA 的两个孩子
       ↓
⑤ 父节点就是 LCA

核心其实并不复杂。

还有一个非常重要的点

如果你最近是在系统学算法，我建议 LCA 不要只背模板。

下一步最好把这三个东西连起来：

树
 ↓
DFS
 ↓
倍增
 ↓
LCA
 ↓
树上距离
 ↓
树上路径问题

尤其是 “为什么 fa[u][i] != fa[v][i] 才能跳” 搞懂之后，LCA 基本就真正掌握了，而不是死记代码。

4 次查看举报

LAC树上最近公共祖先详解

1. LCA 是什么？

2. 为什么需要 LCA？

3. 最简单的思路

4. 最暴力的方法

5. LCA 的核心：倍增

6. `fa[u][j]` 是什么？

7. 倍增数组怎么计算？

8. DFS 预处理

9. C++ 标准模板

10. 查询 LCA

第一步：让两个节点处于同一深度

11. 怎么快速跳？

12. 第二步：如果已经相同

13. 第三步：一起往上跳

14. 为什么是“还不是同一个节点”？

15. 完整 LCA 函数

16. 用一个具体例子跑一遍

第一步：深度

第二步：从大到小跳

17. 为什么时间复杂度是 O(log n)？

18. 完整代码

19. LCA 最应该记住的 4 个东西

① `depth`

② `fa[u][0]`

③ 倍增公式

④ LCA 查询

20. LCA 和树上距离

21. 倍增 LCA 的整体思维

还有一个非常重要的点

0 条评论

目前还没有评论...

LAC树上最近公共祖先详解

1. LCA 是什么？

2. 为什么需要 LCA？

3. 最简单的思路

4. 最暴力的方法

5. LCA 的核心：倍增

6. fa[u][j] 是什么？

7. 倍增数组怎么计算？

8. DFS 预处理

9. C++ 标准模板

10. 查询 LCA

第一步：让两个节点处于同一深度

11. 怎么快速跳？

12. 第二步：如果已经相同

13. 第三步：一起往上跳

14. 为什么是“还不是同一个节点”？

15. 完整 LCA 函数

16. 用一个具体例子跑一遍

第一步：深度

第二步：从大到小跳

17. 为什么时间复杂度是 O(log n)？

18. 完整代码

19. LCA 最应该记住的 4 个东西

① depth

② fa[u][0]

③ 倍增公式

④ LCA 查询

20. LCA 和树上距离

21. 倍增 LCA 的整体思维

还有一个非常重要的点

0 条评论

目前还没有评论...

还没有账户？

登录

6. `fa[u][j]` 是什么？

① `depth`

② `fa[u][0]`