【模板】最近公共祖先（LCA）

GitHub跳转原题关系图返回列表

用非递归建树和倍增祖先表回答大规模最近公共祖先询问。

OJ: luogu

题目 ID: P3379

难度:普及+/提高-

标签:LCA倍增树python

日期: 2026-07-17 02:00

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

给定根树，回答任意两点的最近公共祖先。

思路

先求深度和父亲。up[j][u] 表示 u 的 2^j 级祖先。查询时先把较深节点提升到同层，再从最高层向下尝试同时跳跃。

Python 知识

  • array("i") 保存每层祖先表，避免 n log n 个 Python 整数对象。
  • 前向星 head/to/next_edge 让 50 万节点的邻接结构保持紧凑。
  • 分块写出答案，避免一次性保存几十万字符串。

代码

python
import sys
from array import array


input = sys.stdin.buffer.readline
n, queries, root = map(int, input().split())
head = array("i", [-1]) * (n + 1)
to = array("i", [0]) * (2 * n - 2)
next_edge = array("i", [0]) * (2 * n - 2)
edge_count = 0


def add_edge(u, v):
    global edge_count
    to[edge_count] = v
    next_edge[edge_count] = head[u]
    head[u] = edge_count
    edge_count += 1


for _ in range(n - 1):
    u, v = map(int, input().split())
    add_edge(u, v)
    add_edge(v, u)

parent = array("i", [0]) * (n + 1)
depth = array("i", [0]) * (n + 1)
depth[root] = 1
order = array("i", [root])
index = 0
while index < n:
    node = order[index]
    index += 1
    edge = head[node]
    while edge != -1:
        neighbor = to[edge]
        if neighbor != parent[node]:
            parent[neighbor] = node
            depth[neighbor] = depth[node] + 1
            order.append(neighbor)
        edge = next_edge[edge]

ancestors = [parent]
for _ in range(1, n.bit_length()):
    previous = ancestors[-1]
    ancestors.append(array("i", (previous[previous[node]] for node in range(n + 1))))


def lca(x, y):
    if depth[x] < depth[y]:
        x, y = y, x
    difference = depth[x] - depth[y]
    bit = 0
    while difference:
        if difference & 1:
            x = ancestors[bit][x]
        difference >>= 1
        bit += 1
    if x == y:
        return x
    for level in range(len(ancestors) - 1, -1, -1):
        if ancestors[level][x] != ancestors[level][y]:
            x = ancestors[level][x]
            y = ancestors[level][y]
    return parent[x]


output = sys.stdout.write
answers = []
for _ in range(queries):
    x, y = map(int, input().split())
    answers.append(str(lca(x, y)))
    if len(answers) == 8192:
        output("\n".join(answers) + "\n")
        answers.clear()
output("\n".join(answers))

原有 C++ 版本仍保留：

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

const int MAXN = 500005;
const int MAXE = 1000005;
const int LOG = 20;

int n, m, root;
int head[MAXN], to[MAXE], nxt[MAXE], edge_cnt;
int depth_node[MAXN];
int up[MAXN][LOG + 1];

void add_edge(int u, int v) {
    edge_cnt++;
    to[edge_cnt] = v;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

void read_input() {
    cin >> n >> m >> root;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        add_edge(u, v);
        add_edge(v, u);
    }
}

void build_lca() {
    queue<int> que;
    que.push(root);
    depth_node[root] = 1;
    up[root][0] = 0;

    while (!que.empty()) {
        int u = que.front();
        que.pop();

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

        for (int i = head[u]; i != 0; i = nxt[i]) {
            int v = to[i];
            if (v == up[u][0]) {
                continue;
            }
            up[v][0] = u;
            depth_node[v] = depth_node[u] + 1;
            que.push(v);
        }
    }
}

int lca(int x, int y) {
    if (depth_node[x] < depth_node[y]) {
        swap(x, y);
    }

    int diff = depth_node[x] - depth_node[y];
    for (int j = LOG; j >= 0; j--) {
        if ((diff & (1 << j)) != 0) {
            x = up[x][j];
        }
    }

    if (x == y) {
        return x;
    }

    for (int j = LOG; j >= 0; j--) {
        if (up[x][j] != up[y][j]) {
            x = up[x][j];
            y = up[y][j];
        }
    }

    return up[x][0];
}

void solve() {
    build_lca();

    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        cout << lca(x, y) << '\n';
    }
}

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

    read_input();
    solve();

    return 0;
}

复杂度

预处理 O(n log n)，每次查询 O(log n)，空间 O(n log n)。

总结

LCA 倍增的两个动作是“提升深度”和“从高位向下试跳”。