Bài 24.3. Thuật toán Binary Lifting tìm LCA

Chào mừng các bạn quay trở lại với series về Cấu trúc dữ liệu và Giải thuật! Hôm nay, chúng ta sẽ khám phá một vấn đề kinh điển trên cây và một thuật toán mạnh mẽ để giải quyết nó một cách hiệu quả: tìm Tổ tiên chung thấp nhất (Lowest Common Ancestor - LCA) bằng thuật toán Binary Lifting, hay còn gọi là Nhảy nhị phân.

LCA là một trong những bài toán cơ bản nhưng cực kỳ quan trọng trong lập trình trên cây. Nó xuất hiện như một bài toán con trong rất nhiều vấn đề phức tạp khác, từ xử lý truy vấn đường đi trên cây, đến các thuật toán trên đồ thị phức tạp hơn. Việc nắm vững cách tìm LCA là chìa khóa để giải quyết nhiều bài toán nâng cao.

Tổ tiên chung thấp nhất (LCA) là gì?

Định nghĩa một cách ngắn gọn và dễ hiểu: Tổ tiên chung thấp nhất (LCA) của hai nút $u$ và $v$ trong một cây là nút thấp nhất (có độ sâu lớn nhất) mà vừa là tổ tiên của $u$, vừa là tổ tiên của $v$.

Tổ tiên: Một nút $p$ là tổ tiên của $c$ nếu $p$ nằm trên đường đi từ gốc đến $c$ (hoặc $p$ chính là $c$).
Chung: Tổ tiên chung của $u$ và $v$ là một nút vừa là tổ tiên của $u$, vừa là tổ tiên của $v$. Nút gốc của cây luôn là một tổ tiên chung (trừ trường hợp $u$ hoặc $v$ là gốc).
Thấp nhất: Trong số tất cả các tổ tiên chung đó, nút nào có độ sâu lớn nhất chính là LCA.

Ví dụ đơn giản: Trong cây sau:

LCA(4, 5) là 2.
LCA(4, 7) là 2.
LCA(5, 6) là 1.
LCA(7, 7) là 7.
LCA(3, 6) là 3.

Tại sao cần thuật toán hiệu quả?

Nếu chỉ cần tìm LCA cho một cặp nút duy nhất, chúng ta có thể dùng các phương pháp đơn giản hơn:

Tìm đường đi từ gốc đến $u$ và đường đi từ gốc đến $v$. LCA là nút cuối cùng chung trên hai đường đi này.
Đưa hai nút về cùng độ sâu, sau đó cùng lúc đi lên từ cả hai nút cho đến khi gặp nhau. Nút gặp nhau chính là LCA.

Các phương pháp này đều mất thời gian O(N) hoặc O(Height) cho mỗi truy vấn (với N là số nút, Height là chiều cao cây). Nếu có Q truy vấn LCA, tổng thời gian sẽ là O(NQ) hoặc O(HeightQ). Với cây lớn và nhiều truy vấn (ví dụ, N, Q lên đến $10^5$), cách này sẽ quá chậm và vượt quá giới hạn thời gian cho phép.

Chúng ta cần một phương pháp có thời gian truy vấn nhanh hơn, lý tưởng là O(log N) hoặc O(1) sau một bước tiền xử lý. Binary Lifting chính là một giải pháp tuyệt vời cho điều này với thời gian truy vấn O(log N).

Binary Lifting: Ý tưởng cốt lõi

Ý tưởng chính của Binary Lifting dựa trên việc sử dụng các lũy thừa của 2 để "nhảy" trên cây một cách nhanh chóng. Thay vì chỉ lưu trữ nút cha trực tiếp (parent[u]), chúng ta sẽ tiền xử lý và lưu trữ nút tổ tiên thứ $2^k$ của mỗi nút $u$.

Tại sao lại là lũy thừa của 2? Bởi vì mọi số nguyên dương đều có thể biểu diễn dưới dạng tổng các lũy thừa phân biệt của 2 (hệ nhị phân). Tương tự, việc di chuyển bất kỳ số bước nào lên trên cây có thể được phân rã thành các bước "nhảy" có độ dài là lũy thừa của 2. Ví dụ, để nhảy lên 13 bước, chúng ta có thể nhảy lên $2^3=8$ bước, sau đó $2^2=4$ bước, và cuối cùng $2^0=1$ bước (8 + 4 + 1 = 13).

Chúng ta sẽ cần một bảng (thường là mảng 2D) để lưu thông tin này:

parent_up[u][k] = Nút tổ tiên thứ $2^k$ của nút $u$.

$k = 0$: parent_up[u][0] = nút cha trực tiếp của $u$. (Tổ tiên thứ $2^0 = 1$)
$k = 1$: parent_up[u][1] = tổ tiên thứ $2^1 = 2$ của $u$. Nút này chính là tổ tiên thứ $2^0$ của tổ tiên thứ $2^0$ của $u$. Nghĩa là, parent_up[u][1] = parent_up[parent_up[u][0]][0].
$k > 1$: Tổng quát, để tìm tổ tiên thứ $2^k$ của $u$, chúng ta nhảy lên $2^{k-1}$ bước từ $u$ để đến nút $v = \text{parent_up}[u][k-1]$, sau đó từ $v$ lại nhảy tiếp $2^{k-1}$ bước nữa. Tổng cộng là $2^{k-1} + 2^{k-1} = 2^k$ bước. Do đó, công thức truy hồi là: parent_up[u][k] = parent_up[parent_up[u][k-1]][k-1]

Số mũ $k$ tối đa cần thiết là bao nhiêu? Nếu cây có $N$ nút, chiều cao tối đa có thể là $N-1$. Tổ tiên xa nhất có thể là gốc. Chúng ta cần nhảy tối đa khoảng $N-1$ bước. Số mũ $k$ lớn nhất sao cho $2^k \le N-1$ là $k \approx \log_2(N-1)$. Chúng ta thường dùng $k_{max} = \lfloor \log_2 N \rfloor$ hoặc $\lceil \log_2 N \rceil$ để an toàn. Với $N = 10^5$, $\log_2 10^5 \approx 16.6$, nên $k_{max}$ khoảng 17-18 là đủ.

Các bước thực hiện Binary Lifting

Thuật toán Binary Lifting được chia làm hai giai đoạn chính:

Tiền xử lý (Preprocessing): Xây dựng bảng parent_up và tính độ sâu của các nút.
Truy vấn (Query): Sử dụng bảng parent_up để tìm LCA của hai nút bất kỳ.

Giai đoạn 1: Tiền xử lý

Chúng ta cần hai thông tin cho mỗi nút: độ sâu (depth[u]) và nút cha trực tiếp (parent_up[u][0]). Thông tin này có thể thu thập dễ dàng bằng một lần duyệt DFS hoặc BFS từ nút gốc.

Sau khi có độ sâu và nút cha trực tiếp, chúng ta dùng phương pháp Quy hoạch động (Dynamic Programming) để xây dựng bảng parent_up cho các giá trị $k > 0$.

Khởi tạo:
- depth[root] = 0.
- parent_up[root][0] = -1 (hoặc một giá trị đặc biệt chỉ gốc).
- parent_up[u][0] cho $u \ne \text{root}$ được xác định từ DFS/BFS.
- Điền -1 vào các ô parent_up[u][k] nếu nút đó không tồn tại (ví dụ: nút gốc không có tổ tiên ở bất kỳ khoảng cách nào).
Tính DP:
- Duyệt qua các giá trị $k$ từ 1 đến $k_{max}$.
- Duyệt qua tất cả các nút $u$ từ 0 đến $N-1$.
- Nếu parent_up[u][k-1] tồn tại (không phải -1), thì parent_up[u][k] = parent_up[parent_up[u][k-1]][k-1].
- Nếu parent_up[u][k-1] không tồn tại, thì parent_up[u][k] = -1.

Thời gian cho giai đoạn tiền xử lý này là O(N * $k_{max}$) = O(N log N) vì có N nút và $k_{max} \approx \log_2 N$.

Giai đoạn 2: Truy vấn LCA(u, v)

Để tìm LCA của hai nút $u$ và $v$, chúng ta thực hiện các bước sau:

Cân bằng độ sâu: Đảm bảo $u$ là nút có độ sâu lớn hơn hoặc bằng độ sâu của $v$. Nếu depth[u] < depth[v], hoán đổi $u$ và $v$. Mục đích là để di chuyển nút sâu hơn lên ngang hàng với nút nông hơn.
Nâng nút sâu hơn lên: Di chuyển nút $u$ lên trên sao cho depth[u] bằng depth[v]. Khoảng cách cần nhảy là diff = depth[u] - depth[v]. Chúng ta biểu diễn diff dưới dạng nhị phân và sử dụng bảng parent_up để nhảy. Duyệt $k$ từ $k_{max}$ xuống 0. Nếu bit thứ $k$ trong diff bằng 1 (nghĩa là diff có chứa $2^k$), chúng ta nhảy $u$ lên $2^k$ bước: u = parent_up[u][k]. Sau bước này, $u$ và $v$ ở cùng độ sâu.
Kiểm tra nếu đã gặp nhau: Nếu sau khi cân bằng độ sâu, $u = v$, điều đó có nghĩa là nút ban đầu $v$ (nút nông hơn) chính là tổ tiên của nút ban đầu $u$. Trong trường hợp này, $v$ chính là LCA.
Nhảy đồng thời: Nếu $u \ne v$, chúng ta cần tìm tổ tiên chung đầu tiên của chúng. Hiện tại $u$ và $v$ đang ở cùng độ sâu, dưới LCA. Chúng ta muốn nhảy cả hai lên càng cao càng tốt mà không vượt qua LCA. Tức là, chúng ta muốn tìm nút tổ tiên của $u$ và $v$ mà gần LCA nhất từ phía dưới. Chúng ta duyệt $k$ từ $k_{max}$ xuống 0. Nếu parent_up[u][k] tồn tại và parent_up[u][k] != parent_up[v][k], điều này có nghĩa là tổ tiên thứ $2^k$ của $u$ và $v$ là khác nhau. Tuyệt vời! Điều này ngụ ý rằng LCA phải nằm ở đâu đó phía trên các nút parent_up[u][k] và parent_up[v][k]. Để tiếp tục tìm kiếm LCA từ vị trí cao hơn nhưng vẫn dưới LCA thực sự, chúng ta nhảy cả $u$ và $v$ lên các vị trí này: u = parent_up[u][k], v = parent_up[v][k]. Nếu parent_up[u][k] == parent_up[v][k], điều này có nghĩa là tổ tiên thứ $2^k$ của $u$ và $v$ là giống nhau. Nếu nhảy, chúng ta có thể sẽ nhảy lên đến hoặc vượt qua LCA. Chúng ta không muốn điều đó ở bước này, vì chúng ta muốn tìm nút ngay dưới LCA. Vì vậy, chúng ta bỏ qua bước nhảy cho giá trị $k$ này và thử với $k$ nhỏ hơn.
Kết quả: Sau khi duyệt hết tất cả các giá trị $k$ từ $k_{max}$ xuống 0, $u$ và $v$ sẽ ở cùng độ sâu và là hai nút ngay dưới LCA. Nút cha trực tiếp của $u$ (hoặc $v$) chính là LCA. Kết quả là parent_up[u][0].

Thời gian cho mỗi truy vấn LCA là O($k_{max}$) = O(log N) vì chúng ta duyệt qua $k$ từ $k_{max}$ xuống 0 (tối đa log N bước) và thực hiện một vài thao tác kiểm tra/nhảy.

Tổng thời gian cho Q truy vấn là O(N log N + Q log N). Tổng không gian là O(N log N) cho bảng parent_up. Đây là sự đánh đổi giữa thời gian tiền xử lý/không gian lưu trữ và thời gian truy vấn.

Triển khai bằng C++

Chúng ta hãy cùng xem xét cách triển khai thuật toán Binary Lifting tìm LCA trong C++.

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

const int MAXN = 100005; // Số nút tối đa
const int LOGN = 18;    // ceil(log2(MAXN)), đủ lớn cho chiều cao cây

vector<int> adj[MAXN]; // Danh sách kề biểu diễn cây
int depth[MAXN];       // Mảng lưu độ sâu của các nút
int parent_up[MAXN][LOGN]; // Bảng Binary Lifting

// Hàm DFS để tính độ sâu và nút cha trực tiếp (2^0-th ancestor)
void dfs(int u, int p, int d) {
    depth[u] = d;
    parent_up[u][0] = p; // Nút cha trực tiếp

    // Duyệt qua các con của u
    for (int v : adj[u]) {
        if (v != p) { // Tránh quay lại nút cha
            dfs(v, u, d + 1);
        }
    }
}

// Hàm tiền xử lý xây dựng bảng parent_up
void preprocess(int n, int root) {
    // Khởi tạo các giá trị parent_up ban đầu là -1 (hoặc nút đặc biệt)
    // Cẩn thận với nút gốc, cha của nó là -1
    for(int i=0; i<=n; ++i) {
        depth[i] = 0; // Reset depth
        for(int j=0; j<LOGN; ++j) {
            parent_up[i][j] = -1;
        }
    }

    // Thực hiện DFS từ gốc để tính depth và parent_up[u][0]
    dfs(root, -1, 0); 

    // Xây dựng bảng parent_up cho k > 0 sử dụng DP
    for (int k = 1; k < LOGN; ++k) {
        for (int i = 0; i < n; ++i) { // Duyệt qua tất cả các nút
            if (parent_up[i][k - 1] != -1) {
                // Tổ tiên thứ 2^k của i là tổ tiên thứ 2^(k-1) 
                // của (tổ tiên thứ 2^(k-1) của i)
                parent_up[i][k] = parent_up[parent_up[i][k - 1]][k - 1];
            }
        }
    }
}

// Hàm tìm LCA của hai nút u và v
int lca(int u, int v) {
    // Bước 1: Cân bằng độ sâu
    // Đảm bảo u có độ sâu lớn hơn hoặc bằng v
    if (depth[u] < depth[v]) {
        swap(u, v);
    }

    // Di chuyển u lên ngang hàng với v
    int diff = depth[u] - depth[v];
    for (int k = LOGN - 1; k >= 0; --k) {
        // Nếu bit thứ k của diff là 1, nhảy lên 2^k bước
        if ((diff >> k) & 1) {
            if (parent_up[u][k] != -1) { // Đảm bảo tổ tiên tồn tại
                 u = parent_up[u][k];
            }
        }
    }

    // Bước 2: Kiểm tra nếu đã gặp nhau (trường hợp một nút là tổ tiên của nút kia)
    if (u == v) {
        return u; // u (hoặc v) chính là LCA
    }

    // Bước 3: Nhảy đồng thời
    // Nhảy u và v lên càng cao càng tốt mà vẫn DƯỚI LCA
    for (int k = LOGN - 1; k >= 0; --k) {
        // Nếu tổ tiên thứ 2^k của u và v khác nhau
        if (parent_up[u][k] != -1 && parent_up[v][k] != -1 && parent_up[u][k] != parent_up[v][k]) {
            // Nhảy cả hai lên
            u = parent_up[u][k];
            v = parent_up[v][k];
        }
        // Nếu parent_up[u][k] == parent_up[v][k], 
        // thì nhảy 2^k bước sẽ đưa ta đến hoặc vượt qua LCA. Bỏ qua k này.
    }

    // Bước 4: Kết quả
    // Sau khi vòng lặp kết thúc, u và v là hai nút NGAY DƯỚI LCA.
    // Nút cha trực tiếp của u (hoặc v) chính là LCA.
    return parent_up[u][0];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n; // Số lượng nút
    cin >> n;

    // Đọc cấu trúc cây (ví dụ: cạnh)
    // Giả sử các nút được đánh số từ 0 đến n-1
    // Cây có n nút sẽ có n-1 cạnh
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u); // Với cây vô hướng
    }

    // Chọn gốc (ví dụ: nút 0)
    int root = 0; 

    // Tiền xử lý
    preprocess(n, root);

    int q; // Số lượng truy vấn LCA
    cin >> q;

    // Thực hiện các truy vấn LCA
    while (q--) {
        int u, v;
        cin >> u >> v;
        cout << "LCA(" << u << ", " << v << ") = " << lca(u, v) << "\n";
    }

    return 0;
}

Giải thích Code C++

Headers và Hằng số:
- iostream, vector, cmath, algorithm là các thư viện chuẩn cần thiết.
- MAXN: Định nghĩa kích thước tối đa cho số nút. Chọn một giá trị đủ lớn.
- LOGN: Giá trị $\lceil \log_2(\text{MAXN}) \rceil$. Đây là số cột cần thiết trong bảng parent_up. ceil(log2(100005)) xấp xỉ 16.6, nên 18 là giá trị an toàn.
Cấu trúc dữ liệu:
- adj[MAXN]: Danh sách kề để lưu trữ cấu trúc cây. adj[u] chứa danh sách các nút kề với u.
- depth[MAXN]: Mảng lưu trữ độ sâu của mỗi nút so với gốc. Gốc có độ sâu 0.
- parent_up[MAXN][LOGN]: Bảng chính cho Binary Lifting. parent_up[u][k] lưu nút tổ tiên thứ $2^k$ của nút u.
Hàm dfs(u, p, d):
- Đây là hàm duyệt sâu truyền thống.
- u: Nút hiện tại đang thăm.
- p: Nút cha của u trong lần duyệt này (để tránh đi ngược lên).
- d: Độ sâu của nút u.
- Trong hàm này, chúng ta gán depth[u] = d và lưu nút cha trực tiếp (p) vào parent_up[u][0].
- Sau đó, duyệt qua các nút kề v của u. Nếu v không phải là p, tức là v là con của u, thì gọi đệ quy dfs(v, u, d + 1).
Hàm preprocess(n, root):
- Thực hiện bước tiền xử lý.
- Đầu tiên, khởi tạo bảng parent_up và mảng depth (thường bằng -1 hoặc 0 tùy ngữ cảnh và cách xử lý gốc).
- Gọi dfs(root, -1, 0) để tính độ sâu và cha trực tiếp cho tất cả các nút. Nút gốc có cha là -1 và độ sâu là 0.
- Tiếp theo, dùng hai vòng lặp lồng nhau để xây dựng bảng parent_up. Vòng ngoài cho k từ 1 đến LOGN-1. Vòng trong cho mỗi nút i từ 0 đến n-1.
- Công thức parent_up[i][k] = parent_up[parent_up[i][k-1]][k-1] được áp dụng. Chúng ta kiểm tra parent_up[i][k-1] != -1 để đảm bảo tổ tiên thứ $2^{k-1}$ của i tồn tại trước khi cố gắng truy cập parent_up từ nó.
Hàm lca(u, v):
- Đây là hàm truy vấn LCA.
- Cân bằng độ sâu: So sánh depth[u] và depth[v]. Nếu u nông hơn v, hoán đổi chúng để u luôn là nút sâu hơn hoặc bằng độ sâu của v.
- Nâng nút sâu hơn: Tính diff = depth[u] - depth[v]. Sử dụng vòng lặp từ k = LOGN-1 xuống 0. Kiểm tra (diff >> k) & 1 (bit thứ k của diff). Nếu là 1, nghĩa là chúng ta cần nhảy lên $2^k$ bước. Cập nhật u = parent_up[u][k].
- Kiểm tra gặp nhau: Sau khi u và v ở cùng độ sâu, nếu u == v, tức là $v$ ban đầu là tổ tiên của $u$ ban đầu, nên $v$ (hoặc $u$) là LCA. Trả về u.
- Nhảy đồng thời: Nếu u != v, chúng ở cùng độ sâu dưới LCA. Lặp từ k = LOGN-1 xuống 0. Điều kiện parent_up[u][k] != -1 && parent_up[v][k] != -1 && parent_up[u][k] != parent_up[v][k] kiểm tra xem tổ tiên thứ $2^k$ của u và v có tồn tại và có khác nhau không. Nếu khác nhau, nhảy cả hai lên: u = parent_up[u][k], v = parent_up[v][k]. Điều quan trọng là chỉ nhảy khi tổ tiên khác nhau.
- Kết quả: Sau vòng lặp nhảy đồng thời, u và v sẽ là hai nút ngay dưới LCA. Cha trực tiếp của bất kỳ nút nào trong hai nút này chính là LCA. Trả về parent_up[u][0].
Hàm main():
- Thiết lập tốc độ đọc/ghi I/O nhanh.
- Đọc số nút n.
- Đọc n-1 cạnh để xây dựng cây. Lưu ý xử lý cho cây vô hướng bằng cách thêm cạnh vào cả hai danh sách kề.
- Chọn một nút làm gốc (ví dụ: 0).
- Gọi preprocess(n, root) để chuẩn bị.
- Đọc số lượng truy vấn q.
- Trong vòng lặp q, đọc hai nút u và v cho mỗi truy vấn, gọi hàm lca(u, v) và in kết quả.

Ví dụ Minh Họa

Hãy xét lại cây ví dụ ở đầu bài:

(Đổi nút 1 thành 0 làm gốc cho dễ code)

Độ sâu: depth[0]=0 depth[1]=1, depth[2]=1 depth[3]=2, depth[4]=2, depth[5]=2 depth[6]=3

parent_up[u][0]: parent_up[0][0] = -1 parent_up[1][0] = 0 parent_up[2][0] = 0 parent_up[3][0] = 1 parent_up[4][0] = 1 parent_up[5][0] = 2 parent_up[6][0] = 4

Bảng parent_up[u][k] (ví dụ nhỏ): k=0: như trên k=1 (2^1=2 bước): parent_up[0][1] = -1 (tổ tiên 2 bước của gốc không tồn tại) parent_up[1][1] = parent_up[parent_up[1][0]][0] = parent_up[0][0] = -1 parent_up[2][1] = parent_up[parent_up[2][0]][0] = parent_up[0][0] = -1 parent_up[3][1] = parent_up[parent_up[3][0]][0] = parent_up[1][0] = 0 parent_up[4][1] = parent_up[parent_up[4][0]][0] = parent_up[1][0] = 0 parent_up[5][1] = parent_up[parent_up[5][0]][0] = parent_up[2][0] = 0 parent_up[6][1] = parent_up[parent_up[6][0]][0] = parent_up[4][0] = 1

k=2 (2^2=4 bước): parent_up[3][2] = parent_up[parent_up[3][1]][1] = parent_up[0][1] = -1 parent_up[4][2] = parent_up[parent_up[4][1]][1] = parent_up[0][1] = -1 parent_up[5][2] = parent_up[parent_up[5][1]][1] = parent_up[0][1] = -1 parent_up[6][2] = parent_up[parent_up[6][1]][1] = parent_up[1][1] = -1

Truy vấn: LCA(6, 5)

u = 6, v = 5. depth[6] = 3, depth[5] = 2. depth[6] > depth[5], không hoán đổi.
Cân bằng độ sâu: diff = depth[6] - depth[5] = 3 - 2 = 1. Duyệt k từ LOGN-1 xuống 0. k=17 (ví dụ LOGN=18): (1 >> 17) & 1 = 0. Bỏ qua. ... k=1: (1 >> 1) & 1 = 0. Bỏ qua. k=0: (1 >> 0) & 1 = 1. Bit 0 là 1. Nhảy $u=6$ lên $2^0=1$ bước. u = parent_up[6][0] = 4. Sau bước này, $u=4$, $v=5$. depth[4] = 2, depth[5] = 2. Độ sâu đã cân bằng.
Kiểm tra gặp nhau: u = 4, v = 5. $u \ne v$.
Nhảy đồng thời: $u=4, v=5$, độ sâu 2. Duyệt k từ LOGN-1 xuống 0. ... k=1: parent_up[4][1] = 0, parent_up[5][1] = 0. parent_up[4][1] == parent_up[5][1]. Không nhảy. k=0: parent_up[4][0] = 1, parent_up[5][0] = 2. parent_up[4][0] != parent_up[5][0]. Nhảy cả hai lên. u = parent_up[4][0] = 1. v = parent_up[5][0] = 2. Sau bước này, $u=1$, $v=2$.
Kết quả: Vòng lặp k kết thúc. $u=1$. Trả về `parent_up[u][0] = parent_up[1][0] = 0$. LCA(6, 5) = 0. (Trong cây gốc 0, đây là đúng).

Truy vấn: LCA(3, 6)

u=3, v=6. depth[3]=2, depth[6]=3$.depth[3] < depth[6]. Hoán đổi:u=6,v=3`.
Cân bằng độ sâu: diff = depth[6] - depth[3] = 3 - 2 = 1$. k=0: Bit 0 là 1. Nhảy $u=6$ lên $2^0=1$ bước.u = parent_up[6][0] = 4. Sau bước này, $u=4$, $v=3$.depth[4]=2,depth[3]=2`. Độ sâu cân bằng.
Kiểm tra gặp nhau: $u=4 \ne v=3$.
Nhảy đồng thời: $u=4, v=3$, độ sâu 2. Duyệt k từ LOGN-1 xuống 0. ... k=1: parent_up[4][1] = 0, parent_up[3][1] = 0. parent_up[4][1] == parent_up[3][1]. Không nhảy. k=0: parent_up[4][0] = 1, parent_up[3][0] = 1. parent_up[4][0] == parent_up[3][0]. Không nhảy.
Kết quả: Vòng lặp k kết thúc. $u=4$. Trả về `parent_up[u][0] = parent_up[4][0] = 1$. LCA(3, 6) = 1. (Trong cây gốc 0, đây là đúng).

Các ví dụ này cho thấy cách thuật toán sử dụng các bước nhảy nhị phân để nhanh chóng di chuyển lên cây và xác định LCA.

Ưu điểm và Nhược điểm

Ưu điểm:
- Thời gian truy vấn rất nhanh: O(log N) cho mỗi truy vấn sau tiền xử lý. Điều này cực kỳ hữu ích khi có nhiều truy vấn trên cùng một cây.
- 相對簡單實作 ( Relatively simple to implement ): Cốt lõi là DP và nhảy bit, không cần cấu trúc dữ liệu phức tạp khác.
Nhược điểm:
- Thời gian tiền xử lý: O(N log N).
- Không gian lưu trữ: O(N log N) cho bảng parent_up. Với N rất lớn ($> 10^6$), không gian có thể trở thành vấn đề.

Comments

There are no comments at the moment.