Chuyên đề: Bài toán Tổ tiên chung gần nhất (LCA) - Nguyễn Như Thắng

Toàn tập chuyên đề bài toán Tổ tiên chung gần nhất (LCA). Hướng dẫn các thuật toán Nâng nhị phân, Bảng thưa và nhiều bài tập vận dụng có lời giải.

• Tác giả: Nguyễn Như Thắng
• Trường học: Trường THPT Chuyên tỉnh Lào Cai
• Chuyên ngành: Tin học
• Đề tài: Tổ tiên chung gần nhất (LCA)
• Loại tài liệu: Chuyên đề Hội thảo khoa học
• Năm xuất bản: 2020

Tóm tắt

I. Khái niệm cơ bản về Tổ tiên chung gần nhất LCA

Tổ tiên chung gần nhất (LCA - Lowest Common Ancestor) là một trong những bài toán cổ điển trong lý thuyết đồ thị và khoa học máy tính. LCA của hai đỉnh u và v trên một cây được định nghĩa là đỉnh w có độ sâu lớn nhất sao cho w vừa là tổ tiên của u vừa là tổ tiên của v. Bài toán này xuất hiện thường xuyên trong các kỳ thi lập trình như IOI, VOI và các cuộc thi ICPC. Để hiểu rõ LCA, chúng ta cần nắm vững các khái niệm: cây DFS, quan hệ cha-con, độ sâu của đỉnh, và tổ tiên chung. Trong một cây gốc, mỗi đỉnh có một cha duy nhất (ngoại trừ gốc), và các tổ tiên của một đỉnh là tất cả các đỉnh nằm trên đường đi từ nó đến gốc cây.

1.1. Định nghĩa LCA và các khái niệm liên quan

LCA là đỉnh chung có độ sâu lớn nhất của hai đỉnh u và v. Độ sâu được tính từ gốc cây đến đỉnh đó. Nếu một đỉnh là tổ tiên của chính nó, thì LCA(u, u) = u. Đối với hai đỉnh khác nhau, chúng ta tìm đỉnh cao nhất (gần gốc nhất) mà cả hai đều là con cháu của nó.

1.2. Tầm quan trọng của LCA trong các bài toán cây

LCA là nền tảng để giải quyết nhiều bài toán phức tạp trên cây như: tính khoảng cách giữa hai đỉnh, tìm đường đi trên cây, và xử lý các truy vấn trên cây. Hiểu rõ LCA giúp học sinh tiếp cận các kỹ thuật nâng cao như Binary Lifting, Sparse Table, và Heavy Light Decomposition.

II. Các phương pháp giải bài toán LCA

Có nhiều cách để giải bài toán tìm LCA, mỗi phương pháp có ưu và nhược điểm riêng. Phương pháp đơn giản nhất là duyệt tham lam, nhưng nó không hiệu quả với các truy vấn lớn. Phương pháp Binary Lifting (Nâng nhị phân) cho phép trả lời truy vấn trong O(log n) sau khi chuẩn bị O(n log n). Kỹ thuật Sparse Table cũng cung cấp độ phức tạp O(log n) trên truy vấn. Phương pháp Euler Tour chuyển đổi bài toán LCA thành bài toán RMQ (Range Minimum Query) trên mảng. Tarjan's Off-line LCA xử lí các truy vấn ngoại tuyến một cách hiệu quả. Lựa chọn phương pháp phù hợp phụ thuộc vào constraints của bài toán và yêu cầu về hiệu suất.

2.1. Phương pháp Binary Lifting Nâng nhị phân

Binary Lifting hoạt động bằng cách lưu trữ 2^i-ths tổ tiên của mỗi đỉnh. Với mảng up[u][i] biểu diễn 2^i-ths tổ tiên của u, chúng ta có thể nhanh chóng nhảy lên. Để tìm LCA(u, v), đầu tiên đưa cả hai đỉnh về cùng độ sâu, sau đó nhảy cùng lúc cho đến khi gặp tổ tiên chung.

2.2. Kỹ thuật Sparse Table và RMQ

Sparse Table cho phép trả lời các truy vấn RMQ (Range Minimum Query) trong O(1). Bằng cách chuyển đổi cây thành Euler Tour, bài toán LCA trở thành tìm giá trị tối thiểu trong khoảng, vì LCA tương ứng với độ sâu nhỏ nhất trong dãy độ sâu Euler.

III. Ứng dụng LCA trong các bài toán thực tế

LCA không chỉ là bài toán lý thuyết mà còn có nhiều ứng dụng thực tiễn. Trong các bài toán về cây cơ sở hạ tầng, mạng máy tính, hoặc hệ thống phân cấp, chúng ta cần tính khoảng cách giữa hai nút. Bài toán tính khoảng cách dist(u, v) = depth[u] + depth[v] - 2*depth[LCA(u, v)] là ứng dụng trực tiếp. Các bài toán về Marathon, du lịch thành phố, dạo chơi đồng cỏ đều sử dụng LCA như một công cụ quan trọng. Bài toán cây đổi gốc yêu cầu tính toán lại LCA khi gốc cây thay đổi. Các bài toán cập nhật thông tin trên cây kết hợp LCA với Segment Tree hoặc BIT để xử lí các truy vấn cập nhật và lấy giá trị trên đường đi.

3.1. Tính khoảng cách và đường đi trên cây

Để tính khoảng cách giữa hai đỉnh u và v, chúng ta sử dụng công thức: distance = depth[u] + depth[v] - 2 * depth[LCA(u, v)]. Điều này cho phép giải quyết các bài toán về đường đi ngắn nhất trên cây một cách hiệu quả.

3.2. LCA trong các bài toán cây phức tạp

Trong bài toán cây đổi gốc, khi thay đổi gốc cây, LCA của hai đỉnh cũng thay đổi. Các bài toán dạo chơi trên cây, cập nhật thông tin kết hợp LCA với các cấu trúc dữ liệu như Segment Tree để xử lí truy vấn trên đường đi từ u đến v.

IV. Hướng dẫn học tập và phát triển kỹ năng LCA

Để thành thạo bài toán LCA, học sinh nên bắt đầu từ những bài tập cơ bản, hiểu rõ cách hoạt động của từng phương pháp. Nên thực hành với các bài toán từ dễ đến khó, từ bài tập cơ bản như tìm LCA đơn giản, đến các bài phức tạp hơn như Marathon racing, upgrade network, hoặc update tree. Kỹ năng đọc hiểu đề bài và nhận diện khi nào cần sử dụng LCA cũng rất quan trọng. Học sinh cần kết hợp LCA với các kỹ thuật khác như DFS/BFS, Quy hoạch động trên cây, Segment Tree, và Binary Indexed Tree. Tham gia các cuộc thi lập trình và giải các bài toán trên các nền tảng như SPOJ, Codeforces, VOI sẽ giúp nâng cao kỹ năng.

4.1. Lộ trình học tập LCA từ cơ bản đến nâng cao

Bắt đầu với lý thuyết cơ bản về cây DFS và độ sâu. Tiếp theo, học Binary Lifting vì đây là phương pháp dễ hiểu và mạnh mẽ. Sau đó, nâng cao với Sparse Table, Euler Tour, và Tarjan's Algorithm. Cuối cùng, áp dụng LCA vào các bài toán phức tạp kết hợp với các cấu trúc dữ liệu khác.

4.2. Nguồn tài liệu và bài tập ôn luyện

Các bài tập từ IOI, VOI, ICPC và SPOJ cung cấp những thách thức thực tế. Nên giải ít nhất 15 bài toán liên quan đến LCA ở các mức độ khác nhau. Học sinh cũng nên nghiên cứu các bài viết chuyên sâu về kỹ thuật Heavy Light Decomposition và Dynamic Tree để mở rộng hiểu biết về cây.

Trích đoạn nội dung tài liệu

Mở đầu Dạng bài về “Tổ tiên chung gần nhất” cũng khá phổ biến, đây đều là các dạng bài không dễ, đòi hỏi học sinh có tư duy khá, nhiều bài đòi hỏi học sinh sáng tạo mới vận dụng được. Học sinh cần có một số kiến thức để đảm bảo học được chuyên đề này là: cơ bản về phương pháp Quy hoạch động trên cây; Đồ thị cơ bản, duyệt đồ thị; kĩ thuật bảng thưa (Sparse table), cấu trúc dữ liệu (Segment tree, BIT, DSU). Trong quá trình dạy đội tuyển lớp HSG lớp 11, đội tuyển HSG Quốc gia. Từ các bài toán dạng này, cũng cho học sinh ôn lại các kiến thức liên quan khác để giải bài toán LCA như: cấu trúc dữ liệu sparse table, segment tree,…; ôn lại bài toán RMQ; kĩ thuật Heavy light decomposition; kĩ thuật duỗi cây thành mảng (Euler tour); duyệt đồ thị; Quy hoạch động trên cây;… 2.

Một số khái niệm, kiến thức cơ bản - Cây DFS: Quá trình duyệt đồ thị theo chiều sâu (DFS) bắt đầu từ đỉnh 𝑠 cho ta một cây DFS gốc 𝑠. - Quan hệ cha-con trên cây DFS: Khi duyệt DFS, nếu từ đỉnh 𝑢 ta gọi hàm tới thăm đỉnh 𝑣 thì đỉnh 𝑢 là đỉnh cha đỉnh 𝑣. Ví dụ: Đỉnh 1 là cha của các đỉnh 2,3,4. Đỉnh 12,13 là con của đỉnh 10.

- Quan hệ tổ tiên-con cháu: Được định nghĩa đệ quy như sau: + Đỉnh 𝑢 là tổ tiên của chính nó. + Đỉnh cha của đỉnh 𝑢 là tổ tiên của đỉnh 𝑢. + Cha của tổ tiên của 𝑢 cũng là tổ tiên của 𝑢. Ta thấy, đỉnh 𝑢 là tổ tiên của tất cả các đỉnh trong nhánh cây DFS gốc 𝑢.

Ví dụ: Đỉnh 7 là tổ tiên của các đỉnh 7,10,11,12,13 và cả chính nó. Đỉnh 6 là tổ tiên của đỉnh 6,8,9. - Độ sâu: Là khoảng cách đến đỉnh gốc (được tính bằng số đỉnh, hoặc số cạnh, không phải là trọng số của cạnh). Đỉnh gốc của cây DFS quy ước độ sâu là 1.

Ví dụ: Đỉnh 3 có độ sâu là 2; đỉnh 12,13 có độ sâu là 5. - Tổ tiên chung: Đỉnh 𝑤 là tổ tiên của đỉnh 𝑢 và 𝑣 thì 𝑤 được gọi là tổ tiên chung của 𝑢 và 𝑣. Ví dụ: Đỉnh 3 là tổ tiên chung của đỉnh 12 và đỉnh 13. - Định nghĩa tổ tiên chung gần nhất (LCA) trên wiki: Trong lý thuyết đồ thị và khoa học máy tính, LCA của 2 đỉnh 𝑢, 𝑣 trên cây hoặc đồ thị có hướng không chu trình (DAG) gốc 𝑇 là đỉnh 𝑤 sâu nhất (hay đỉnh xa gốc nhất) mà nhận cả 𝑢, 𝑣 làm con cháu, chúng ta coi một đỉnh cũng chính là tổ tiên của chính nó.

Ví dụ: Đỉnh 3 là tổ tiên chung gần nhất của đỉnh 7 và 9. Đỉnh 10 là tổ tiên chung gần nhất của 12,13. Trang 5 Chuyên đề Hội thảo khoa học các trường THPT Chuyên khu vực Duyên Hải và ĐBBB 2020 - Nhận xét thấy 𝐿𝐶𝐴(𝑢, 𝑣) là đỉnh đầu tiên gặp nhau của đường đi từ 𝑢 về gốc và đường đi từ 𝑣 về gốc. Từ nhận xét này ta sẽ hình thành các cách giải bài toán LCA.

Dạng bài toán nào có thể cần đến LCA Trong chuyên đề này, tôi tập trung vào các dạng bài sau: - Các bài tập về tìm kiếm, cập nhật thông tin của các đỉnh nằm trên đường đi đơn từ 𝑢 đến 𝑣. Ví dụ như tính khoảng cách giữa các cặp đỉnh trên cây (cây có trọng số, không có trọng số). - Dạng bài LCA kết hợp cấu trúc dữ liệu như: Segment tree, Binay index tree, Disjoint set union,…. - Dạng bài LCA kết hợp với quy hoạch động trên cây, cây khung, cầu-khớp,… - Dạng bài LCA có đổi gốc.

- Đánh dấu, cộng dồn trên cây có áp dụng LCA. Theo nhận định của tác giả thì các dạng bài khó sẽ là dạng bài phải biết kết hợp thêm các dạng bài khác về cây, kết hợp cấu trúc dữ liệu; các bài cần học sinh có sự sáng tạo mới phát hiện ra cần áp dụng dạng bài toán LCA như thế nào,… 4. Các phương pháp giải bài toán LCA Để trình bày một số phương pháp giải bài toán LCA, tác giả đưa ra ví dụ cây có gốc là 1 như dữ liệu cho sau: Dữ liệu vào Kết quả ra Giải thích 13 lca(2,4)=1 12 lca(12,13)=10 13 lca(2,5)=1 14 lca(8,9)=6 35 lca(12,11)=7 36 lca(6,7)=3 37 68 69 7 10 7 11 10 12 10 13 6 24 Cho đồ thị gồm 13 đỉnh, 12 12 13 cạnh, và 6 câu hỏi truy vấn tìm 25 LCA. 89 12 11 67 Trang 6 Chuyên đề Hội thảo khoa học các trường THPT Chuyên khu vực Duyên Hải và ĐBBB 2020 4.

Duyệt tham lam Nhận xét rằng để tìm tổ tiên chung gần nhất của 2 đỉnh 𝑢, 𝑣 thì từ 2 đỉnh này, ta đi lên từng bước một về phía gốc cây. Đến vị trí gặp nhau đầu tiên thì đó chính là tổ tiên chung gần nhất. Phương pháp: Bước 1: Di chuyển đỉnh có độ sâu lớn hơn đến khi 2 đỉnh có cùng độ sâu. Bước 2: Nếu 2 đỉnh chưa gặp nhau thì ta cùng di chuyển chúng đến khi gặp nhau thì lập tức dừng lại, đó chính là LCA của chúng.

Các làm này khá lâu nếu trong trường hợp cây DFS suy biến thành dạng đường thẳng. Đánh giá độ phức tạp của thuật toán: - Độ phức tạp tiền xử lí (duyệt DFS): 𝑶(𝑵). - Độ phức tạp của một truy vấn là: 𝑶(𝑵).  Độ phức tạp thuật toán chung: 𝑶(𝑵 ∗ 𝑸).

Chương trình tham khảo: #include <bits/stdc++.h> using namespace std; int n, q, par[100005], depth[100005]; vector<int> adj[100005]; ///duyet DFS de xac dinh do xau va tim cha cua cac dinh void dfs(int u, int p, int d) { depth[u] = d; par[u] = p; for(int v : adj[u]) { if(par[u] == v) continue; dfs(v, u, d + 1); } } int lca(int u, int v) { ///Tim LCA theo kieu Brute force if(depth[u] < depth[v]) swap(u, v); while(depth[u] > depth[v]) u = par[u]; while(u != v) { u = par[u]; v = par[v]; } return u; } int main() { cin >> n; for(int i = 1; i < n; i++) { int u, v; cin >> u >> v; adj[u]. Chia căn Nhận xét rằng cách làm Brute Force trên khá lâu vì mỗi lần ta chỉ đi lên được một đỉnh. Trong cách làm sau đây, ta tiền xử lí bằng cách chia cây có độ cao depth[u ]  1 H thành các √𝐻 tầng. Đỉnh có độ sâu 𝑑𝑒𝑝𝑡ℎ[𝑢] thì được xếp vào tầng.

Khi đó nếu 𝑢, 𝑣 chưa cùng tầng thì ta nhảy theo tầng, nếu cùng tầng thì ta nhảy theo cha của nó để đến khi gặp nhau. Đánh giá độ phức tạp của thuật toán: - Độ phức tạp tiền xử lí: 𝑶(𝑵 ∗ √𝑵 ). - Độ phức tạp của một truy vấn là: 𝑶(√𝑵 ).  Độ phức tạp thuật toán chung: 𝑶(𝑵 ∗ √𝑵 + 𝑸 ∗ √𝑵 ).

Ví dụ: H=5 và [√𝐻] = 2 Tầng 1 Tầng 2 Tầng 3 Chương trình tham khảo: #include <bits/stdc++.h> using namespace std; int n, q, H, s, par[100005], depth[100005], T[100005]; vector<int> adj[100005]; ///duyet DFS de xac dinh do xau va tim cha cua cac dinh void dfs0(int u, int p, int d) { depth[u] = d; H = max(H, d); par[u] = p; for(int v : adj[u]) { if(par[u] == v) Trang 8 Chuyên đề Hội thảo khoa học các trường THPT Chuyên khu vực Duyên Hải và ĐBBB 2020 continue; dfs0(v, u, d + 1); } } void dfs(int u, int p, int d) { ///tim to tien o tang tren cua u depth[u] = d; par[u] = p; if(depth[u] < s) T[u] = 1; else if((depth[u] + 1) % s) T[u] = T[par[u]]; else T[u] = par[u]; for(int v : adj[u]) { if(par[u] == v) continue; dfs(v, u, d + 1); } } int lca(int u, int v) { ///Tim LCA chia can while(T[u] != T[v]) if(depth[u] > depth[v]) u = T[u]; else v = T[v]; while(u != v) { if(depth[u] > depth[v]) u = par[u]; else v = par[v]; } return u; } int main() { //freopen("LCA_sqrt.inp", "r", stdin); cin >> n; for(int i = 1; i < n; i++) { int u, v; cin >> u >> v; adj[u].push_back(u); } dfs0(1, 0, 1); s = sqrt(H); dfs(1, 0, 1); cin >> q; while(q--) { int u, v; cin >> u >> v; cout << "lca(" << u << "," << v << ")=" << lca(u, v) << "\n"; } } Trang 9 Chuyên đề Hội thảo khoa học các trường THPT Chuyên khu vực Duyên Hải và ĐBBB 2020 4. Kĩ thuật bảng thưa (Sparse table) Đây là kĩ thuật hay dùng nhất trong giải các bài toán về LCA. Nhận xét rằng mọi số nguyên dương đều có thể biểu dưới dạng nhị phân. Nhận xét này khá quan trọng, từ đó ta có thể cải tiến cách làm của các thuật toán đã giới thiệu ở trên bằng cách nhảy lên các lũy thừa của 2 (binary lifting), từ đó việc tìm 𝐿𝐶𝐴(𝑢, 𝑣) chỉ có độ phức tạp 𝑂(log(𝑁)).

20 Khi đó để 𝑢 nhảy lên tổ tiên 𝑣 trên nó 5 bậc thì ta nhảy đến cha trước đó 22 bậc, sau đó nhảy tiếp cha 20 bậc. Ta sẽ sử dụng bảng thưa (Sparse table), cha thứ 2 𝑗 của đỉnh 𝑖 là 𝑇[𝑖][𝑗]. Định nghĩa Sparse table theo công thức truy hồi như sau: 𝑇[𝑢][0] = 𝑝𝑎𝑟[𝑢] Cha cấp 20 { 𝑇[𝑢][𝑖] = 𝑇[𝑇[𝑢][𝑖 − 1]][𝑖 − 1] Cha cấp 2𝑖 (Vì 2𝑖 = 2𝑖−1 + 2𝑖−1 ) Đánh giá độ phức tạp của thuật toán: - Độ phức tạp tiền xử lí (xây dựng bảng thưa) : 𝑶(𝑵 ∗ 𝒍𝒐𝒈(𝑵)) - Độ phức tạp của một truy vấn là: 𝑶(𝒍𝒐𝒈(𝑵)).  Độ phức tạp thuật toán chung: 𝑶(𝑵 ∗ 𝒍𝒐𝒈(𝑵) + 𝑸 ∗ 𝒍𝒐𝒈(𝑵)).

Chương trình tham khảo: #include <bits/stdc++.h> using namespace std; int n, q, depth[100005], T[100005][17]; vector<int> adj[100005]; void dfs(int u, int p) { ///tim to tien o tang tren cua u depth[u] = depth[p] + 1; T[u][0] = p; for(int i = 1; i < 17; i++) T[u][i] = T[T[u][i - 1]][i - 1]; for(int v : adj[u]) { if(v == p) continue; dfs(v, u); } } int lca(int u, int v) { ///Tim LCA Sparse Table if(depth[u] < depth[v]) swap(u, v); for(int i = 16; i >= 0; i--) ///nhay den cung do sau if(depth[T[u][i]] >= depth[v]) u = T[u][i]; if(u == v) return u; for(int i = 16; i >= 0; i--)///nhay den LCA if(T[u][i] != T[v][i]) { u = T[u][i]; v = T[v][i]; Trang 10 Chuyên đề Hội thảo khoa học các trường THPT Chuyên khu vực Duyên Hải và ĐBBB 2020 } return T[u][0]; } int main() { cin >> n; for(int i = 1; i < n; i++) { int u, v; cin >> u >> v; adj[u].