Tìm Tổ Tiên Chung Gần Nhất (LCA) Trong Cấu Trúc Cây

Trong lý thuyết đồ thị và khoa học máy tính, Tổ tiên Chung Gần nhất (Least Common Ancestor - LCA) là một khái niệm cơ bản với nhiều ứng dụng. Bài viết này sẽ đi sâu vào định nghĩa, các phương pháp giải quyết, và một số ví dụ minh họa về LCA.

Kiến thức Nền tảng

Cây (Tree): Một cấu trúc dữ liệu dạng đồ thị đặc biệt, trong đó bất kỳ hai đỉnh nào cũng chỉ có một đường đi duy nhất giữa chúng. Cây có N đỉnh sẽ có N-1 cạnh và không chứa chu trình. Một cây thường có một đỉnh gốc được chỉ định; nếu không, ta có thể chọn một đỉnh bất kỳ (thường là đỉnh 1) làm gốc.
Tổ tiên (Ancestor): Đỉnh Y là tổ tiên của đỉnh X nếu Y nằm trên đường đi từ X đến đỉnh gốc của cây. Đỉnh cha trực tiếp là một trường hợp đặc biệt của tổ tiên.
Bảng Sparse Table (ST): Một cấu trúc dữ liệu cho phép truy vấn nhanh các phép toán trên đoạn (ví dụ: tìm giá trị lớn nhất/nhỏ nhất) trong thời gian $$O(1)$$ sau khi tiền xử lý $O(N \log N)$ . Khái niệm sử dụng các bước nhảy lũy thừa của 2 để tăng tốc độ truy vấn là điểm tương đồng giữa ST và phương pháp tối ưu LCA.

Tổ tiên Chung Gần nhất (LCA) là gì?

Tổ tiên Chung Gần nhất của hai đỉnh U và V trên cây là đỉnh chung có độ sâu lớn nhất (tức là gần U và V nhất) mà cả U và V đều có đỉnh đó là tổ tiên. Ví dụ, xét một cây đơn giản sau, với 1 là gốc:

$$LCA(4,5) = 2$$
$$LCA(6,7) = 3$$
$$LCA(4,7) = 1$$
$$LCA(5,2) = 2$$ (Nếu một đỉnh là tổ tiên của đỉnh kia, thì chính đỉnh đó là LCA).

Giải pháp LCA vét cạn (Naive)

Một phương pháp đơn giản để tìm LCA có độ phức tạp thời gian tồi nhất là $$O(N)$$ cho mỗi truy vấn.

Tiền xử lý

Đầu tiên, chúng ta cần chạy thuật toán Tìm kiếm theo Chiều sâu (DFS) bắt đầu từ đỉnh gốc (ví dụ: đỉnh 1) để tính độ sâu của mỗi đỉnh và lưu trữ đỉnh cha trực tiếp của nó. Gán độ sâu của gốc là 1.

vector<vector<int>> adj; // Danh sách kề của cây
vector<int> depth;     // Lưu độ sâu của các đỉnh
vector<int> parent;    // Lưu cha trực tiếp của các đỉnh

void dfs_preprocess(int current_node, int current_parent, int current_depth) {
    depth[current_node] = current_depth;
    parent[current_node] = current_parent;

    for (int neighbor : adj[current_node]) {
        if (neighbor != current_parent) {
            dfs_preprocess(neighbor, current_node, current_depth + 1);
        }
    }
}

Sau bước này, chúng ta có độ sâu depth[u] và cha trực tiếp parent[u] cho mọi đỉnh u.

Truy vấn LCA

Để tìm $$LCA(node_A, node_B)$$ :

Cân bằng độ sâu: Đưa đỉnh có độ sâu lớn hơn lên cao hơn cho đến khi cả hai đỉnh có cùng độ sâu. Nếu $$depth[node_A] < depth[node_B]$$ , đổi chỗ node_A và node_B. Sau đó, di chuyển node_A lên dần bằng cách gán $$node_A = parent[node_A]$$ cho đến khi $$depth[node_A] == depth[node_B]$$ .
Tìm tổ tiên chung: Khi cả hai đỉnh đã có cùng độ sâu, di chuyển cả node_A và node_B lên một bước tại một thời điểm bằng cách gán $$node_A = parent[node_A]$$ và $$node_B = parent[node_B]$$ cho đến khi $$node_A == node_B$$ . Đỉnh mà chúng gặp nhau chính là LCA.

int find_lca_naive(int node_A, int node_B) {
    // 1. Cân bằng độ sâu
    if (depth[node_A] < depth[node_B]) {
        swap(node_A, node_B);
    }
    while (depth[node_A] > depth[node_B]) {
        node_A = parent[node_A];
    }

    // 2. Tìm tổ tiên chung
    while (node_A != node_B) {
        node_A = parent[node_A];
        node_B = parent[node_B];
    }
    return node_A; // node_A và node_B hiện tại là LCA
}

Thuật toán này dễ hiểu nhưng không hiệu quả cho các bài toán có số lượng truy vấn lớn $$Q$$ (ví dụ: $$Q=10^5$$ ), vì mỗi truy vấn có thể mất $$O(N)$$ thời gian.

Tối ưu hóa thuật toán LCA bằng Binary Lifting

Điểm nghẽn về hiệu suất của phương pháp vét cạn nằm ở việc di chuyển từng bước một. Để tăng tốc độ, chúng ta có thể sử dụng kỹ thuật "Binary Lifting" (nhảy nhị phân), cho phép nhảy $$2^k$$ bước trong một lần. Kỹ thuật này giảm độ phức tạp truy vấn từ $$O(N)$$ xuống $O(\log N)$ .

Tiền xử lý

Chúng ta cần một mảng ancestor_jump[u][k] để lưu trữ tổ tiên thứ $$2^k$$ của đỉnh u. $ancestor\_jump[u][0]$ sẽ là cha trực tiếp của u. Với $$k > 0$$ , tổ tiên thứ $$2^k$$ của u là tổ tiên thứ $2^{k-1}$ của tổ tiên thứ $2^{k-1}$ của u. Công thức truy hồi là: $ancestor\_jump[u][k] = ancestor\_jump[ancestor\_jump[u][k-1]][k-1]$ .

Chúng ta có thể thực hiện tiền xử lý trong hai bước:

Thực hiện DFS để tính depth[u] và ancestor_jump[u][0] cho tất cả u.
Sử dụng vòng lặp để tính các giá trị ancestor_jump[u][k] còn lại.

const int MAX_NODES = 100005;
const int LOG_MAX_NODES = 20; // ceil(log2(MAX_NODES))

vector<vector<int>> adj_list;
vector<int> node_depth;
vector<vector<int>> ancestor_jump; // ancestor_jump[u][k] = 2^k-th ancestor of u

void dfs_binary_lifting(int current, int parent_node, int current_depth) {
    node_depth[current] = current_depth;
    ancestor_jump[current][0] = parent_node; // Tổ tiên 2^0 (cha trực tiếp)

    for (int neighbor : adj_list[current]) {
        if (neighbor != parent_node) {
            dfs_binary_lifting(neighbor, current, current_depth + 1);
        }
    }
}

void build_ancestor_table(int num_nodes) {
    // Khởi tạo các mảng
    adj_list.resize(num_nodes + 1);
    node_depth.resize(num_nodes + 1);
    ancestor_jump.assign(num_nodes + 1, vector<int>(LOG_MAX_NODES + 1, 0));

    // Bắt đầu DFS từ gốc (giả sử 1 là gốc và 0 là cha của gốc)
    dfs_binary_lifting(1, 0, 1);

    // Điền bảng ancestor_jump
    for (int k = 1; k <= LOG_MAX_NODES; ++k) {
        for (int u = 1; u <= num_nodes; ++u) {
            ancestor_jump[u][k] = ancestor_jump[ancestor_jump[u][k-1]][k-1];
        }
    }
}

Truy vấn LCA

Để tìm $$LCA(node_A, node_B)$$ với Binary Lifting:

Cân bằng độ sâu: Giống như phương pháp vét cạn, chúng ta muốn hai đỉnh có cùng độ sâu. Nếu $$node_A$$ sâu hơn $$node_B$$ , đổi chỗ chúng. Sau đó, di chuyển $$node_B$$ lên trên bằng cách nhảy các bước $$2^k$$ lớn nhất có thể mà không vượt quá độ sâu của $$node_A$$ .
Tìm tổ tiên chung: Nếu sau khi cân bằng độ sâu, $$node_A == node_B$$ , thì $$node_A$$ chính là LCA. Ngược lại, chúng ta di chuyển cả $$node_A$$ và $$node_B$$ lên cùng lúc. Bắt đầu từ bước nhảy lớn nhất xuống 0, nếu $ancestor\_jump[node_A][k]$ khác $ancestor\_jump[node_B][k]$ , thì chúng ta nhảy lên $$2^k$$ bước cho cả hai. Sau khi hoàn thành vòng lặp, $$node_A$$ và $$node_B$$ sẽ là hai đỉnh ngay dưới LCA của chúng. Do đó, LCA chính là cha trực tiếp của $$node_A$$ (hoặc $$node_B$$ ).

int find_lca_binary_lifting(int node_A, int node_B) {
    // Đảm bảo node_A có độ sâu nhỏ hơn hoặc bằng node_B
    if (node_depth[node_A] > node_depth[node_B]) {
        swap(node_A, node_B);
    }

    // 1. Di chuyển node_B lên để cân bằng độ sâu với node_A
    for (int k = LOG_MAX_NODES; k >= 0; --k) {
        if (node_depth[node_B] - (1 << k) >= node_depth[node_A]) {
            node_B = ancestor_jump[node_B][k];
        }
    }

    // Nếu sau khi cân bằng, chúng gặp nhau, thì đó là LCA
    if (node_A == node_B) {
        return node_A;
    }

    // 2. Cùng di chuyển lên cho đến khi cha của chúng khác nhau
    for (int k = LOG_MAX_NODES; k >= 0; --k) {
        if (ancestor_jump[node_A][k] != ancestor_jump[node_B][k]) {
            node_A = ancestor_jump[node_A][k];
            node_B = ancestor_jump[node_B][k];
        }
    }

    // Khi vòng lặp kết thúc, node_A và node_B là con trực tiếp của LCA
    return ancestor_jump[node_A][0];
}

Ứng dụng của LCA

Ví dụ 1: Tổng trọng số trên đường đi trên cây

Giả sử mỗi đỉnh có một giá trị value[u]. Để tính tổng giá trị các đỉnh trên đường đi từ X đến Y:

Thực hiện DFS để tính tổng tiền tố prefix_sum[u], là tổng giá trị từ gốc đến u (bao gồm u).

Tổng trên đường đi từ X đến Y là: $prefix\_sum[X] + prefix\_sum[Y] - 2 \times prefix\_sum[LCA(X,Y)] + value[LCA(X,Y)]$ .

Công thức này đảm bảo rằng giá trị của $$LCA(X,Y)$$ chỉ được tính một lần (nó được cộng hai lần qua $prefix\_sum[X]$ và $prefix\_sum[Y]$ , trừ đi hai lần, sau đó cộng lại một lần).

Ví dụ 2: Quy hoạch động trên cây (Tree Differencing/Đánh dấu đường đi)

Kỹ thuật này hữu ích khi cần thực hiện nhiều phép toán cập nhật trên các đường đi trong cây và sau đó truy vấn trạng thái cuối cùng của các đỉnh. Ví dụ, đếm số đường đi đi qua mỗi đỉnh.

Khi một đường đi từ X đến Y được thêm vào, chúng ta đánh dấu các điểm sau trên một mảng diff_array:

int lca_val = find_lca_binary_lifting(X, Y);
diff_array[X]++;
diff_array[Y]++;
diff_array[lca_val]--;
if (ancestor_jump[lca_val][0] != 0) { // Đảm bảo không phải gốc
    diff_array[ancestor_jump[lca_val][0]]--;
}

Sau khi xử lý tất cả các đường đi, ta chạy một DFS khác để lan truyền các giá trị diff_array từ dưới lên trên:

void accumulate_diffs(int current, int parent_node) {
    for (int neighbor : adj_list[current]) {
        if (neighbor != parent_node) {
            accumulate_diffs(neighbor, current);
            diff_array[current] += diff_array[neighbor];
        }
    }
    // diff_array[current] lúc này chứa tổng số đường đi đi qua đỉnh current
}

Giá trị cuối cùng của diff_array[u] sẽ là số lượng đường đi đi qua đỉnh u.

Kết luận

Tổ tiên Chung Gần nhất (LCA) là một khái niệm quan trọng trong các thuật toán liên quan đến cây. Với phương pháp Binary Lifting, chúng ta có thể giải quyết các bài toán LCA một cách hiệu quả, với thời gian tiền xử lý $O(N \log N)$ và thời gian truy vấn $O(\log N)$ . LCA không chỉ giúp tính toán độ dài đường đi giữa hai đỉnh mà còn là nền tảng cho nhiều kỹ thuật phức tạp hơn như cây phân cấp, tổng tiền tố trên cây, và quy hoạch động trên cây.

Thẻ: lca Binary Lifting Tree Algorithms Graph Theory Competitive Programming

Đăng vào ngày 23 tháng 5 lúc 15:15

Thành phố Cuồng loạn

Tìm Tổ Tiên Chung Gần Nhất (LCA) Trong Cấu Trúc Cây

Kiến thức Nền tảng

Tổ tiên Chung Gần nhất (LCA) là gì?

Giải pháp LCA vét cạn (Naive)

Tiền xử lý

Truy vấn LCA

Tối ưu hóa thuật toán LCA bằng Binary Lifting

Tiền xử lý

Truy vấn LCA

Ứng dụng của LCA

Ví dụ 1: Tổng trọng số trên đường đi trên cây

Ví dụ 2: Quy hoạch động trên cây (Tree Differencing/Đánh dấu đường đi)

Kết luận

Thẻ Phổ Biến