¶ Các phương pháp giải bài toán LCA
Tác giả: Khúc Anh Tuấn
Đôi lời về tác giả: Khúc Anh Tuấn được coi là huyền thoại của Competitive Programming Việt Nam với nhiều thành tích khủng:
- HCB IOI 2006
- Người Việt Nam duy nhất từng đạt được Đỏ Target trên Topcoder (max rating là hơn 3000, chỉ có khoảng chưa đến 100 người trên thế giới đạt được).
- Rank 2 Facebook Hackercup
- Người Việt Nam duy nhất từng lọt vào chung kết Google Code Jam.
- Giữ kỷ lục thi ACM ICPC World final của Việt Nam tính đến thời điểm 2011 (rank 17 toàn cầu).
Bài viết này được đưa lên thư viện VNOI cũ và được mình khôi phục lại sau nhiều năm thất truyền.
Trước khi đọc bài viết này, bạn cần đọc bài viết: Bài toán RMQ và bài toán LCA để nắm được những khái niệm cơ bản.
Để giải bài toán LCA ta có thể chuyển sang bài toán RMQ tương ứng và có thể giải bằng một số cách khác nhau. Trong bài viết này chúng ta sẽ đề cập tới một số phương pháp giải bài toán LCA một cách trực tiếp.
¶ Bài toán LCA (Least Common Ancestor):
Input: 1 cây với đỉnh.
Truy vấn: với 2 nút , bất kỳ của cây , truy vấn cho biết cha chung gần nhất của 2 đỉnh , trong cây , tức là cho biết đỉnh xa gốc nhất là cha của cả và .
¶ Cách 1 - Sparse Table
Từ cây đầu vào ta có thể xây dựng được mảng với cho ta biết nút cha của nút . Sau đó ta có thể xây dựng mảng với cho ta biết nút tổ tiên thứ của nút . Xây dựng mảng mất sử dụng phương pháp QHĐ. Gọi là khoảng cách tới gốc của nút . Để xác định ta thực hiện các bước sau:
- Giả sử , ta thay bằng một nút tổ tiên của đến khi .
- Khi ta thay và bằng 2 nút tổ tiên tương ứng sao cho vẫn thỏa mãn đến khi . Khi đó ta có được kết quả cần tìm.
Tất nhiên trong quá trình thay một nút bằng nút tổ tiên của nó, ta sẽ sử dụng mảng để có thể nhảy một lần được nhiều bước. Khi đó độ phức tạp của thuật toán sẽ là .
¶ Cách 2 - Euler Tour + Interval Tree
Từ cây đầu vào ta sử dụng thủ tục DFS để xây dựng 2 mảng:
- với cho ta biết thứ tự gọi thủ tục DFS cho đỉnh .
- với cho ta biết thứ tự thoát khỏi thủ tục DFS cho đỉnh .
Từ 2 mảng và ta có thể thấy điều kiện cần và đủ để là cha của là và . Do đó thao tác chất vấn thực chất là tìm một đỉnh sao cho :
- lớn nhất có thể (hoặc nhỏ nhất có thể ).
2 điều kiện đầu đảm bảo sẽ là cha chung của và , điều kiện thứ 3 đảm bảo sẽ là đỉnh xa gốc nhất, tức .
Xây dựng mảng với cho ta biết với là đỉnh sao cho . Ta hoàn toàn có thể xây dựng mảng trong thời gian . Như vậy ta cần tìm trong mảng con phần tử cuối cùng sao cho giá trị của nó không nhỏ hơn . Ta có thể sử dụng cấu trúc dữ liệu Interval Tree để làm việc này, mỗi nút của cây Interval sẽ lưu giá trị lớn nhất của một đoạn và khi thực hiện thủ tục DFS trên cây Interval ta ưu tiên đi sang cây con bên phải. Khi biết được giá trị (và cả ) của đỉnh cần tìm rồi ta sẽ dễ dàng biết được đỉnh đó.
Độ phức tạp của thuật toán này cũng giống như thuật toán 1 với thời gian là như chỉ mất bộ nhớ.
¶ Cách 3
Cũng tương tự cách 2 ta khởi tạo các mảng và . Mảng với cho ta biết đỉnh sao cho . Như vậy ta cần tìm trong mảng con . Ta có thể sử dụng phương pháp chặt nhị phân kết hợp đệ quy để làm cận (khá tốt) như sau:
-
Xét thủ tục
Find_LCA(left, right, u, v : Integer)tìm cha chung gần nhất của , trong mảng con . Không mất tính tổng quát giả sử .-
Nếu thì và đây là trường hợp dễ dàng tìm ra đáp án.
-
Nếu , gọi . Xét phần tử chính giữa đoạn sẽ có các khả năng sau:
- : sẽ là cha chung của và nhưng chưa chắc đã là . Hiển nhiên nên ta gọi đệ quy:
Find_LCA( mid, right, u, v). - : là cha của nhưng không phải là cha của . Vì vậy , ta gọi đệ quy:
Find_LCA( left, mid, i, v). - : đỉnh là đỉnh được rẽ nhánh ra từ một nút cha nào đó của , nhưng ta hoàn toàn chưa biết nút cha này nằm dưới hay trên . Ta có thể xử lý theo 2 cách: gọi đệ quy
Find_LCA(left,right,cha(u),cha(v))hoặc lấyj = Find_LCA(left,mid,i,u)và sẽ rơi vào 2 trường hợp đầu.
- : sẽ là cha chung của và nhưng chưa chắc đã là . Hiển nhiên nên ta gọi đệ quy:
-
Thuật toán trên nếu chỉ thực hiện 2 trường hợp đầu thì độ phức tạp cho mỗi lần chất vấn là , còn nếu chỉ thực hiện trường hợp 3 thì độ phức tạp sẽ là . Qua khảo sát bằng việc chạy chương trình cho thấy thời gian thực hiện trung bình của thuật toán này ngang với các thuật toán với độ phức tạp . Thuật toán này tuy có độ phức tạp lớn nhưng lại là phương pháp tiết kiệm bộ nhớ và cài đặt dễ dàng nên đây là thuật toán có ứng dụng cao trong làm bài.
¶ Cách 4 - Heavy Light Decomposition
Sử dụng Heavy Light Decomposition.
Xuất phát từ trường hợp suy biến của cây: mỗi nút của cây chỉ có đúng 1 con (trừ 1 nút lá không có con). Với một cây suy biến ta hoàn toàn có thể tìm trong thời gian (đỉnh nào gần gốc hơn trong 2 đỉnh , sẽ là ). Tư tưởng của Heavy Light Decomposition sẽ là chia cây ban đầu ra thành nhiều cây suy biến.
Những đoạn cùng màu là một cây suy biến. Nếu coi mỗi cây suy biến là một đỉnh thì ta sẽ được một cây mới gọi là cây rút gọn. Sau đây là một cách chia cây để cây rút gọn thu được có độ cao với là số nút của cây ban đầu:
- Xuất phát từ đỉnh gốc
- Với mỗi đỉnh nếu là lá thì nó sẽ là kết thúc của một cây suy biến
- Nếu không ta sẽ phát triển tiếp cây suy biến này xuống đỉnh con có trọng lượng lớn nhất, các đỉnh con khác sẽ là nút gốc của những cây suy biến mới. Trọng lượng của một nút được định nghĩa là số nút nhận nút đó là tổ tiên (hiểu một cách trực quan thì nếu coi mỗi nút có một “sức nặng” thì trọng lượng của một nút chính là “sức nặng” mà nút đó phải gánh).
Chứng minh:
-
Gọi là hàm cho ta chiều cao tối đa của một cây rút gọn có đỉnh. Ta sẽ chứng minh .
-
Với thì .
-
Giả sử điều cần chứng minh đã đúng đến .
-
Với một cây có đỉnh và nút gốc sẽ có các cây con với số đỉnh là . Giả sử . Ta có
. -
Theo cách xây dựng cây thì :
Mà:- ...
Vậy (Điều phải chứng minh).
Để thực hiện chất vấn ta lần lượt nhảy từ và trở về gốc của cây. Từ một đỉnh ta thực hiện lần lượt một bước nhảy dài tới gốc của cây suy biến chứa nó và một bước nhảy ngắn tới nút cha (qua đó chuyển sang cây suy biến mới). Sau khi xác định được cây suy biến chứa , ta có thể xác định được đỉnh , tương ứng là nút đầu tiên ta gặp khi nhảy từ , tới cây suy biến chứa . Sau đó chỉ cần sử dụng một phép so sánh xem hay gần gốc hơn là có thể xác định được .
Tuy về ý tưởng ta quan tâm nhiều đến việc chia cây ban đầu ra thành nhiều cây suy biến nhưng về mặt cài đặt, ta chỉ cần quan tâm với mỗi nút của cây đầu vào, nút gốc của cây suy biến chứa nó là nút nào. Dễ thấy khi thực hiện thủ tục DFS (có ưu tiên gọi đệ quy tới nút con có trọng lượng lớn nhất trước) các nút sẽ được liệt kê lần lượt theo từng cây suy biến. Vì vậy ta có thể khởi tạo mảng với cho ta biết nút gốc của cây suy biến chứa nút chỉ với .
Thuật toán này sẽ chạy trong thời gian .
Thuật toán này khá linh hoạt và có thể mở rộng ra để ứng dụng vào nhiều bài toán khác trên cây. Để ý rằng nếu cây ban đầu có trọng số ở mỗi cạnh, sau khi chia thành các cây suy biến thì cạnh của mỗi cây suy biến sẽ giống như các phần tử liên tiếp của một mảng. Do đó ta hoàn toàn có thể sử dụng các cấu trúc dữ liệu như Interval Tree để quản lý việc thay đổi hay chất vấn thông tin về các cạnh này. Đây chính là ý tưởng để làm bài QTREE.
¶ Cách 5 - Xử lý offline
Đây là một phương pháp để giải bài toán LCA khi đã biết trước mọi câu hỏi chất vấn. Cách làm này tuy không linh hoạt nhưng thời gian chạy khá nhanh và tiết kiệm bộ nhớ. Tư tưởng của phương pháp này là trả lời các câu chất vấn theo một thứ tự khác dễ dàng hơn. Với mỗi nút của cây ta sẽ lưu nó trong một tập hợp có nhãn. Ban đầu mỗi nút thuộc một tập hợp khác nhau và nhãn của tập hợp chính là chỉ số của nút đó. Sau đó ta thực hiện thủ tục DFS, trước khi thoát ra khỏi thủ tục DFS ta thực hiện 2 thao tác sau :
- Tìm cha chung của với các đỉnh mà thủ tục
DFS(v)đã được thực thi. Đỉnh cha chung chính là nhãn của tập hợp chứa . - Hợp nhất tập hợp chứa với tập hợp chứa và lấy nhãn là .
Ta sẽ chứng minh “Đỉnh cha chung chính là nhãn của tập hợp chứa v”. Giả sử . Sau khi thực thi thủ tục DFS(v) xong, từ thủ tục DFS phải đi về và rẽ xuống để có thể thực hiện DFS(u). Trong quá trình đi về , nó sẽ hợp nhất với cha , ông ,.. rồi với . Do đó nhãn của tập chứa chính là .
Để thực hiện thao tác hợp nhất 2 tập hợp với thời gian ngắn, ta có thể sử dụng cấu trúc disjoint set giống như trong thuật toán Kruskal. Độ phức tạp của phương pháp này là với là số thao tác.