Tổ tiên chung gần nhất (LCA)

Mức độ: Chuyên sâu

Trên một cây có gốc, tổ tiên của u là các đỉnh trên đường từ u đi lên gốc (gồm cả u). Tổ tiên chung gần nhất (LCA) của u và v là tổ tiên chung sâu nhất của cả hai, cũng là chỗ hai đường đi lên gốc gặp nhau. Đường đi giữa u và v trên cây luôn đi lên tới LCA rồi đi xuống, nên LCA trả lời được rất nhiều câu hỏi về đường đi: khoảng cách, cạnh lớn nhất, đỉnh thứ k…

Cách chậm: đi lên từng bước

Đưa đỉnh sâu hơn đi lên cho tới khi hai đỉnh cùng độ sâu, rồi cho cả hai cùng đi lên từng bước tới khi gặp nhau. Mỗi câu hỏi có thể mất n bước (cây là một đường dài), với 10⁵ câu hỏi là 10¹⁰.

Nhảy nhị phân

Như nhảy k bước, lưu len[j][v] là tổ tiên thứ 2^j của v (đi lên 2^j bước): len[0][v] là cha, len[j][v] = len[j - 1][len[j - 1][v]].

Tìm LCA của u và v (giả sử u sâu hơn):

1. Đưa về cùng độ sâu: u cần đi lên d = sau[u] - sau[v] bước. Viết d dạng nhị phân, bit thứ j bằng 1 thì u = len[j][u].
2. Nếu lúc này u = v thì v là LCA.
3. Nhảy cùng lúc: đi j từ lớn đến nhỏ; nếu len[j][u] khác len[j][v] thì nhảy cả hai (u = len[j][u], v = len[j][v]). Nhảy như vậy hai đỉnh vẫn ở dưới LCA. Kết thúc, u và v là hai con của LCA, đáp số là cha của u.

Ở bước 3, nếu len[j][u] = len[j][v] thì đó là một tổ tiên chung, có thể đã vượt quá LCA, nên không nhảy. Cuối cùng u, v đứng ngay dưới LCA: chỉ còn thiếu một bước.

Mỗi câu hỏi khoảng 2 × log₂n bước, chuẩn bị bảng mất n × log₂n.

Python

import sys
du_lieu = sys.stdin.read().split()
n, q = int(du_lieu[0]), int(du_lieu[1])
ke = [[] for _ in range(n + 1)]
for i in range(n - 1):
    u, v = int(du_lieu[2 + 2 * i]), int(du_lieu[3 + 2 * i])
    ke[u].append(v)
    ke[v].append(u)
LOG = max(1, n.bit_length())
sau = [0] * (n + 1)
len_ = [[0] * (n + 1) for _ in range(LOG)]      # len_[j][v]: tổ tiên thứ 2^j
thu_tu, da_tham = [1], [False] * (n + 1)
da_tham[1] = True
for u in thu_tu:                                # BFS từ gốc 1
    for v in ke[u]:
        if not da_tham[v]:
            da_tham[v] = True
            sau[v] = sau[u] + 1
            len_[0][v] = u
            thu_tu.append(v)
len_[0][1] = 1                                  # cha của gốc là chính nó
for j in range(1, LOG):
    truoc, hien = len_[j - 1], len_[j]
    for v in range(1, n + 1):
        hien[v] = truoc[truoc[v]]

def lca(u, v):
    if sau[u] < sau[v]:
        u, v = v, u
    d, j = sau[u] - sau[v], 0
    while d:                                    # đưa u lên cùng độ sâu với v
        if d & 1:
            u = len_[j][u]
        d >>= 1
        j += 1
    if u == v:
        return u
    for j in range(LOG - 1, -1, -1):            # nhảy cùng lúc, luôn ở dưới LCA
        if len_[j][u] != len_[j][v]:
            u, v = len_[j][u], len_[j][v]
    return len_[0][u]

vt = 2 + 2 * (n - 1)
print("\n".join(str(lca(int(du_lieu[vt + 2 * t]), int(du_lieu[vt + 2 * t + 1]))) for t in range(q)))

C++

#include <iostream>
#include <vector>
using namespace std;

int LOG;
vector<int> sau;
vector<vector<int>> len;      // len[j][v]: tổ tiên thứ 2^j

int lca(int u, int v) {
    if (sau[u] < sau[v]) swap(u, v);
    int d = sau[u] - sau[v];
    for (int j = 0; d; j++, d >>= 1)            // đưa u lên cùng độ sâu với v
        if (d & 1) u = len[j][u];
    if (u == v) return u;
    for (int j = LOG - 1; j >= 0; j--)          // nhảy cùng lúc, luôn ở dưới LCA
        if (len[j][u] != len[j][v]) {
            u = len[j][u];
            v = len[j][v];
        }
    return len[0][u];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<vector<int>> ke(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        ke[u].push_back(v);
        ke[v].push_back(u);
    }
    LOG = 1;
    while ((1 << LOG) <= n) LOG++;
    sau.assign(n + 1, 0);
    len.assign(LOG, vector<int>(n + 1, 1));
    vector<int> thuTu = {1};
    vector<bool> daTham(n + 1, false);
    daTham[1] = true;
    for (size_t k = 0; k < thuTu.size(); k++) {   // BFS từ gốc 1
        int u = thuTu[k];
        for (int v : ke[u])
            if (!daTham[v]) {
                daTham[v] = true;
                sau[v] = sau[u] + 1;
                len[0][v] = u;
                thuTu.push_back(v);
            }
    }
    for (int j = 1; j < LOG; j++)
        for (int v = 1; v <= n; v++) len[j][v] = len[j - 1][len[j - 1][v]];
    while (q--) {
        int u, v;
        cin >> u >> v;
        cout << lca(u, v) << "\n";
    }
    return 0;
}

Dùng LCA cho đường đi

Gọi w = LCA(u, v):

Câu hỏi	Cách tính
số cạnh giữa u và v	sau[u] + sau[v] - 2 × sau[w]
tổng độ dài (cây có trọng số)	kc[u] + kc[v] - 2 × kc[w], với kc là khoảng cách từ gốc
x có nằm trên đường u - v không	khoảng cách(u, x) + khoảng cách(x, v) = khoảng cách(u, v)
cạnh lớn nhất trên đường	lưu thêm lon[j][v] là cạnh lớn nhất khi nhảy 2j bước, lấy max khi nhảy
cộng 1 cho mọi đỉnh trên đường u - v	cộng 1 tại u và v, trừ 1 tại w và cha của w, rồi cộng dồn từ lá lên gốc

Luyện tập

Gồm 12 bài, chia thành 4 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.

Nhóm 1. LCA và khoảng cách

Bài 1. Tổ tiên chung gần nhất

Cây có n đỉnh, gốc là đỉnh 1. Dòng đầu có n, q (1 ≤ n, q ≤ 2 × 10⁵), n - 1 dòng sau là các cạnh, q dòng sau mỗi dòng có u, v. Với mỗi câu hỏi, in ra tổ tiên chung gần nhất của u và v.

Ví dụ:

Nhập	In ra
7 4 1 2 1 3 2 4 2 5 5 6 3 7 4 6 6 7 5 5 2 6	2 1 5 2

Kiểm tra: nhập

10 5
1 2
2 3
3 4
2 5
5 6
1 7
7 8
7 9
9 10
4 6
10 8
4 10
3 3
6 5

Xem đáp số

2
7
1
3
5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 2. Khoảng cách trên cây

Cây có n đỉnh. Dòng đầu có n, q (1 ≤ n, q ≤ 2 × 10⁵), n - 1 dòng sau là các cạnh, q dòng sau mỗi dòng có u, v. Với mỗi câu hỏi, in ra số cạnh trên đường đi giữa u và v.

Ví dụ:

Nhập	In ra
7 3 1 2 1 3 2 4 2 5 5 6 3 7 4 6 6 7 1 1	3 5 0

Kiểm tra: nhập

10 4
1 2
2 3
3 4
2 5
5 6
1 7
7 8
7 9
9 10
4 6
10 8
4 10
1 10

Xem đáp số

4
3
6
3

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 3. Khoảng cách có trọng số

Cây có n đỉnh, mỗi cạnh có độ dài. Dòng đầu có n, q (1 ≤ n, q ≤ 2 × 10⁵), n - 1 dòng sau mỗi dòng có u, v, w (1 ≤ w ≤ 10⁹), q dòng sau mỗi dòng có u, v. Với mỗi câu hỏi, in ra tổng độ dài đường đi giữa u và v.

Ví dụ:

Nhập	In ra
5 3 1 2 3 1 3 4 3 4 2 3 5 6 2 4 4 5 1 1	9 8 0

Kiểm tra: nhập

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

Xem đáp số

20
22
0
14

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 4. Có nằm trên đường đi không

Cây có n đỉnh. Dòng đầu có n, q (1 ≤ n, q ≤ 2 × 10⁵), n - 1 dòng sau là các cạnh, q dòng sau mỗi dòng có u, v, x. Với mỗi câu hỏi, in ra YES nếu đỉnh x nằm trên đường đi giữa u và v (kể cả hai đầu), ngược lại NO.

Ví dụ:

Nhập	In ra
7 3 1 2 1 3 2 4 2 5 5 6 3 7 4 6 2 4 6 1 6 7 3	YES NO YES

Kiểm tra: nhập

10 4
1 2
2 3
3 4
2 5
5 6
1 7
7 8
7 9
9 10
4 6 5
4 10 1
8 10 9
3 3 2

Xem đáp số

YES
YES
YES
NO

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 5. Điểm hẹn của ba người

Cây có n đỉnh. Dòng đầu có n, q (1 ≤ n, q ≤ 2 × 10⁵), n - 1 dòng sau là các cạnh, q dòng sau mỗi dòng có a, b, c: vị trí của ba người. Với mỗi câu hỏi, chọn một đỉnh để ba người cùng đi tới sao cho tổng số cạnh ba người phải đi là ít nhất. In ra tổng đó.

Ví dụ:

Nhập	In ra
7 2 1 2 1 3 2 4 2 5 5 6 3 7 4 6 7 4 5 6	6 3

Kiểm tra: nhập

10 3
1 2
2 3
3 4
2 5
5 6
1 7
7 8
7 9
9 10
4 6 10
8 10 3
1 1 1

Xem đáp số

8
6
0

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 2. Tổ tiên thứ k

Bài 6. Tổ tiên thứ k

Cây có n đỉnh, gốc là đỉnh 1. Dòng đầu có n, q (1 ≤ n, q ≤ 2 × 10⁵), n - 1 dòng sau là các cạnh, q dòng sau mỗi dòng có u, k (0 ≤ k ≤ n). Với mỗi câu hỏi, in ra đỉnh đến được khi đi từ u lên phía gốc đúng k bước, hoặc -1 nếu đi quá gốc.

Ví dụ:

Nhập	In ra
7 4 1 2 1 3 2 4 2 5 5 6 3 7 6 2 6 4 7 0 4 2	2 -1 7 1

Kiểm tra: nhập

10 5
1 2
2 3
3 4
2 5
5 6
1 7
7 8
7 9
9 10
4 3
10 2
10 4
6 1
1 1

Xem đáp số

1
7
-1
5
-1

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 7. Đỉnh thứ k trên đường đi

Cây có n đỉnh. Dòng đầu có n, q (1 ≤ n, q ≤ 2 × 10⁵), n - 1 dòng sau là các cạnh, q dòng sau mỗi dòng có u, v, k. Với mỗi câu hỏi, in ra đỉnh thứ k trên đường đi từ u tới v (đỉnh u là thứ 0), hoặc -1 nếu đường đi ngắn hơn k cạnh.

Ví dụ:

Nhập	In ra
7 3 1 2 1 3 2 4 2 5 5 6 3 7 4 7 2 4 7 3 6 4 1	1 3 5

Kiểm tra: nhập

10 4
1 2
2 3
3 4
2 5
5 6
1 7
7 8
7 9
9 10
4 10 3
4 10 6
10 4 5
6 6 0

Xem đáp số

1
10
3
6

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 3. Thông tin trên đường đi

Bài 8. Cạnh nặng nhất trên đường đi

Cây có n đỉnh, mỗi cạnh có trọng số. Dòng đầu có n, q (2 ≤ n ≤ 2 × 10⁵, 1 ≤ q ≤ 2 × 10⁵), n - 1 dòng sau mỗi dòng có u, v, w (1 ≤ w ≤ 10⁹), q dòng sau mỗi dòng có u, v (u khác v). Với mỗi câu hỏi, in ra trọng số lớn nhất của một cạnh trên đường đi giữa u và v.

Ví dụ:

Nhập	In ra
5 3 1 2 3 1 3 4 3 4 2 3 5 6 2 4 4 5 5 1	4 6 6

Kiểm tra: nhập

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

Xem đáp số

9
8
9
7

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 9. Đếm lượt đi qua mỗi đỉnh

Cây có n đỉnh. Có m chuyến đi, chuyến thứ i đi từ u tới v theo đường duy nhất trên cây. Dòng đầu có n, m (1 ≤ n, m ≤ 2 × 10⁵), n - 1 dòng sau là các cạnh, m dòng sau mỗi dòng có u, v. In ra số chuyến đi qua mỗi đỉnh 1, 2, …, n (kể cả đỉnh đầu, đỉnh cuối).

Ví dụ:

Nhập	In ra
7 3 1 2 1 3 2 4 2 5 5 6 3 7 4 6 6 7 3 3	1 2 2 1 2 2 1

Kiểm tra: nhập

10 4
1 2
2 3
3 4
2 5
5 6
1 7
7 8
7 9
9 10
4 6
10 8
4 10
6 6

Xem đáp số

1 2 2 2 1 2 2 1 2 2

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 10. Đếm lượt đi qua mỗi cạnh

Như bài 9 nhưng đếm theo cạnh: in ra số chuyến đi qua từng cạnh, theo đúng thứ tự các cạnh trong dữ liệu vào. Dòng đầu có n, m (2 ≤ n ≤ 2 × 10⁵, 1 ≤ m ≤ 2 × 10⁵), n - 1 dòng sau là các cạnh, m dòng sau mỗi dòng có u, v.

Ví dụ:

Nhập	In ra
7 3 1 2 1 3 2 4 2 5 5 6 3 7 4 6 6 7 3 3	1 1 1 2 2 1

Kiểm tra: nhập

10 4
1 2
2 3
3 4
2 5
5 6
1 7
7 8
7 9
9 10
4 6
10 8
4 10
6 6

Xem đáp số

1 2 2 1 1 1 1 2 2

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 4. Vận dụng

Bài 11. Hai đường đi có giao nhau không

Cây có n đỉnh. Dòng đầu có n, q (1 ≤ n, q ≤ 2 × 10⁵), n - 1 dòng sau là các cạnh, q dòng sau mỗi dòng có a, b, c, d. Với mỗi câu hỏi, in ra YES nếu đường đi a - b và đường đi c - d có ít nhất một đỉnh chung, ngược lại NO.

Ví dụ:

Nhập	In ra
7 3 1 2 1 3 2 4 2 5 5 6 3 7 4 6 1 7 4 5 6 3 4 6 2 2	NO YES YES

Kiểm tra: nhập

10 4
1 2
2 3
3 4
2 5
5 6
1 7
7 8
7 9
9 10
4 6 8 10
3 6 5 7
4 10 9 9
6 6 6 6

Xem đáp số

NO
YES
YES
YES

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 12. Tổ tiên chung của cả nhóm

Cây có n đỉnh, gốc là đỉnh 1. Dòng đầu có n, q (1 ≤ n, q ≤ 2 × 10⁵), n - 1 dòng sau là các cạnh, q dòng sau mỗi dòng bắt đầu bằng k rồi k đỉnh (tổng các k không quá 2 × 10⁵). Với mỗi nhóm, in ra tổ tiên chung gần nhất của cả k đỉnh.

Ví dụ:

Nhập	In ra
7 3 1 2 1 3 2 4 2 5 5 6 3 7 2 4 6 3 4 6 7 1 5	2 1 5

Kiểm tra: nhập

10 4
1 2
2 3
3 4
2 5
5 6
1 7
7 8
7 9
9 10
3 4 6 3
2 8 10
4 4 6 10 2
1 9

Xem đáp số

2
7
1
9

Hướng dẫn giải chi tiết: liên hệ tác giả.

Lời giải chi tiết các bài luyện tập

Đáp số của từng bài ở ngay dưới đề để các bạn tự kiểm tra. Lời giải chi tiết (phân tích, chạy tay, chương trình Python và C++, lưu ý khi làm bài) có trong bộ tài liệu có phí của chuyên đề.

Thầy cô và các bạn muốn mua bộ tài liệu vui lòng liên hệ tác giả qua Zalo 0972465159 hoặc Facebook.