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 skkn 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 skkn 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 skkn 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 skkn 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 skkn 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].