Phân rã Heavy-light (Heavy-light decomposition)¶
Phân rã Heavy-light là một kỹ thuật khá tổng quát cho phép chúng ta giải quyết hiệu quả nhiều bài toán liên quan đến truy vấn trên cây.
Mô tả (Description)¶
Giả sử có một cây $G$ gồm $n$ đỉnh, với một gốc tùy ý.
Bản chất của việc phân rã cây này là chia cây thành nhiều đường đi sao cho chúng ta có thể đến đỉnh gốc từ bất kỳ $v$ nào bằng cách đi qua tối đa $\log n$ đường đi. Ngoài ra, không có đường đi nào trong số này giao nhau với đường đi khác.
Rõ ràng là nếu chúng ta tìm thấy một sự phân rã như vậy cho bất kỳ cây nào, nó sẽ cho phép chúng ta giảm một số truy vấn đơn lẻ có dạng “tính toán thứ gì đó trên đường đi từ $a$ đến $b$” thành một số truy vấn thuộc loại “tính toán thứ gì đó trên đoạn $[l, r]$ của đường đi thứ $k$”.
Thuật toán xây dựng (Construction algorithm)¶
Chúng ta tính toán cho mỗi đỉnh $v$ kích thước của cây con của nó $s(v)$, tức là số lượng đỉnh trong cây con của đỉnh $v$ bao gồm cả chính nó.
Tiếp theo, xem xét tất cả các cạnh dẫn đến các con của một đỉnh $v$. Chúng ta gọi một cạnh là nặng (heavy) nếu nó dẫn đến một đỉnh $c$ sao cho:
Tất cả các cạnh khác được nhãn là nhẹ (light).
Rõ ràng là tối đa một cạnh nặng có thể đi ra từ một đỉnh xuống dưới, bởi vì nếu không thì đỉnh $v$ sẽ có ít nhất hai con có kích thước $\ge \frac{s(v)}{2}$, và do đó kích thước của cây con của $v$ sẽ quá lớn, $s(v) \ge 1 + 2 \frac{s(v)}{2} > s(v)$, điều này dẫn đến mâu thuẫn.
Bây giờ chúng ta sẽ phân rã cây thành các đường đi không giao nhau. Xem xét tất cả các đỉnh mà từ đó không có cạnh nặng nào đi xuống. Chúng ta sẽ đi lên từ mỗi đỉnh như vậy cho đến khi chúng ta đến gốc của cây hoặc đi qua một cạnh nhẹ. Kết quả là, chúng ta sẽ nhận được một số đường đi được tạo thành từ không hoặc nhiều cạnh nặng cộng với một cạnh nhẹ. Đường đi có một đầu ở gốc là một ngoại lệ đối với điều này và sẽ không có cạnh nhẹ. Gọi đây là đường đi nặng (heavy paths) - đây là những đường đi mong muốn của phân rã heavy-light.
Chứng minh tính đúng đắn (Proof of correctness)¶
Đầu tiên, chúng ta lưu ý rằng các đường đi nặng thu được bằng thuật toán sẽ không giao nhau. Trên thực tế, nếu hai đường đi như vậy có chung một cạnh, điều đó có nghĩa là có hai cạnh nặng đi ra khỏi một đỉnh, điều này là không thể.
Thứ hai, chúng ta sẽ chỉ ra rằng đi xuống từ gốc của cây đến một đỉnh tùy ý, chúng ta sẽ thay đổi không quá $\log n$ đường đi nặng trên đường đi. Di chuyển xuống một cạnh nhẹ làm giảm kích thước của cây con hiện tại xuống một nửa hoặc thấp hơn:
Do đó, chúng ta có thể đi qua tối đa $\log n$ cạnh nhẹ trước khi kích thước cây con giảm xuống còn một.
Vì chúng ta có thể di chuyển từ một đường đi nặng sang đường đi khác chỉ thông qua một cạnh nhẹ (mỗi đường đi nặng, ngoại trừ đường đi bắt đầu từ gốc, có một cạnh nhẹ), chúng ta không thể thay đổi đường đi nặng quá $\log n$ lần dọc theo đường đi từ gốc đến bất kỳ đỉnh nào, như yêu cầu.
Hình ảnh sau đây minh họa sự phân rã của một cây mẫu. Các cạnh nặng dày hơn các cạnh nhẹ. Các đường đi nặng được đánh dấu bằng các ranh giới chấm chấm.
Bài toán ví dụ (Sample problems)¶
Khi giải quyết các bài toán, đôi khi thuận tiện hơn khi coi phân rã heavy-light là một tập hợp các đường đi không giao nhau về đỉnh (thay vì các đường đi không giao nhau về cạnh). Để làm điều này, đủ để loại trừ cạnh cuối cùng khỏi mỗi đường đi nặng nếu nó là một cạnh nhẹ, thì không có tính chất nào bị vi phạm, nhưng bây giờ mỗi đỉnh thuộc về chính xác một đường đi nặng.
Dưới đây chúng tôi sẽ xem xét một số nhiệm vụ điển hình có thể được giải quyết với sự trợ giúp của phân rã heavy-light.
Riêng biệt, đáng để chú ý đến bài toán về tổng các số trên đường đi, vì đây là một ví dụ về một vấn đề có thể được giải quyết bằng các kỹ thuật đơn giản hơn.
Giá trị lớn nhất trên đường đi giữa hai đỉnh (Maximum value on the path between two vertices)¶
Cho một cây, mỗi đỉnh được gán một giá trị. Có các truy vấn có dạng $(a, b)$, trong đó $a$ và $b$ là hai đỉnh trong cây, và cần tìm giá trị lớn nhất trên đường đi giữa các đỉnh $a$ và $b$.
Chúng ta xây dựng trước một phân rã heavy-light của cây. Trên mỗi đường đi nặng, chúng ta sẽ xây dựng một segment tree, cho phép chúng ta tìm kiếm một đỉnh có giá trị được gán lớn nhất trong đoạn đã chỉ định của đường đi nặng đã chỉ định trong $\mathcal{O}(\log n)$. Mặc dù số lượng đường đi nặng trong phân rã heavy-light có thể đạt tới $n - 1$, tổng kích thước của tất cả các đường đi bị giới hạn bởi $\mathcal{O}(n)$, do đó tổng kích thước của các segment tree cũng sẽ là tuyến tính.
Để trả lời một truy vấn $(a, b)$, chúng ta tìm tổ tiên chung thấp nhất (lowest common ancestor) của $a$ và $b$ là $l$, bằng bất kỳ phương pháp ưa thích nào. Bây giờ nhiệm vụ đã được giảm xuống còn hai truy vấn $(a, l)$ và $(b, l)$, đối với mỗi truy vấn chúng ta có thể làm như sau: tìm đường đi nặng mà đỉnh thấp hơn nằm trong đó, thực hiện một truy vấn trên đường đi này, di chuyển lên đầu đường đi này, một lần nữa xác định xem chúng ta đang ở trên đường đi nặng nào và thực hiện một truy vấn trên đó, và cứ thế tiếp tục, cho đến khi chúng ta đến đường đi chứa $l$.
Cần cẩn thận với trường hợp khi, ví dụ, $a$ và $l$ nằm trên cùng một đường đi nặng - thì truy vấn tối đa trên đường đi này không nên được thực hiện trên bất kỳ tiền tố nào, mà trên phần bên trong giữa $a$ và $l$.
Trả lời các truy vấn con $(a, l)$ và $(b, l)$ mỗi truy vấn yêu cầu đi qua $\mathcal{O}(\log n)$ đường đi nặng và đối với mỗi đường đi, một truy vấn tối đa được thực hiện trên một số phần của đường đi, một lần nữa yêu cầu $\mathcal{O}(\log n)$ thao tác trong segment tree. Do đó, một truy vấn $(a, b)$ mất thời gian $\mathcal{O}(\log^2 n)$.
Nếu bạn tính toán và lưu trữ thêm các giá trị lớn nhất của tất cả các tiền tố cho mỗi đường đi nặng, thì bạn sẽ nhận được một giải pháp $\mathcal{O}(\log n)$ vì tất cả các truy vấn tối đa đều nằm trên các tiền tố, ngoại trừ tối đa một lần khi chúng ta đến tổ tiên $l$.
Tổng các số trên đường đi giữa hai đỉnh (Sum of the numbers on the path between two vertices)¶
Cho một cây, mỗi đỉnh được gán một giá trị. Có các truy vấn có dạng $(a, b)$, trong đó $a$ và $b$ là hai đỉnh trong cây, và cần tìm tổng các giá trị trên đường đi giữa các đỉnh $a$ và $b$. Một biến thể của nhiệm vụ này là có thể có thêm các thao tác cập nhật thay đổi số được gán cho một hoặc nhiều đỉnh.
Nhiệm vụ này có thể được giải quyết tương tự như bài toán trước về giá trị lớn nhất với sự trợ giúp của phân rã heavy-light bằng cách xây dựng các segment tree trên các đường đi nặng. Tổng tiền tố có thể được sử dụng thay thế nếu không có cập nhật. Tuy nhiên, vấn đề này cũng có thể được giải quyết bằng các kỹ thuật đơn giản hơn.
Nếu không có cập nhật, thì có thể tìm ra tổng trên đường đi giữa hai đỉnh song song với tìm kiếm LCA của hai đỉnh bằng nâng nhị phân — đối với điều này, cùng với tổ tiên thứ $2^k$ của mỗi đỉnh, cũng cần phải lưu trữ tổng trên các đường đi đến các tổ tiên đó trong quá trình tiền xử lý.
Có một cách tiếp cận hoàn toàn khác cho vấn đề này - xem xét Euler tour của cây, và xây dựng một segment tree trên đó. Thuật toán này được xem xét trong một bài viết về một vấn đề tương tự. Một lần nữa, nếu không có cập nhật, việc lưu trữ tổng tiền tố là đủ và không cần segment tree.
Cả hai phương pháp này đều cung cấp các giải pháp tương đối đơn giản lấy $\mathcal{O}(\log n)$ cho một truy vấn.
Tô lại màu các cạnh của đường đi giữa hai đỉnh (Repainting the edges of the path between two vertices)¶
Cho một cây, mỗi cạnh ban đầu được tô màu trắng. Có các cập nhật có dạng $(a, b, c)$, trong đó $a$ và $b$ là hai đỉnh và $c$ là một màu, hướng dẫn rằng tất cả các cạnh trên đường đi từ $a$ đến $b$ phải được tô lại bằng màu $c$. Sau tất cả các lần tô lại, cần báo cáo có bao nhiêu cạnh của mỗi màu đã thu được.
Tương tự như các vấn đề trên, giải pháp đơn giản là áp dụng phân rã heavy-light và tạo một segment tree trên mỗi đường đi nặng.
Mỗi lần tô lại trên đường đi $(a, b)$ sẽ chuyển thành hai bản cập nhật $(a, l)$ và $(b, l)$, trong đó $l$ là tổ tiên chung thấp nhất của các đỉnh $a$ và $b$. $\mathcal{O}(\log n)$ cho mỗi đường đi cho $\mathcal{O}(\log n)$ đường đi dẫn đến độ phức tạp là $\mathcal{O}(\log^2 n)$ cho mỗi cập nhật.
Cài đặt (Implementation)¶
Một số phần của cách tiếp cận được thảo luận ở trên có thể được sửa đổi để làm cho việc triển khai dễ dàng hơn mà không làm mất hiệu quả.
- Định nghĩa về cạnh nặng có thể được thay đổi thành cạnh dẫn đến con có cây con lớn nhất, với sự phá vỡ hòa tùy ý. Điều này có thể dẫn đến việc một số cạnh nhẹ được chuyển đổi thành nặng, điều đó có nghĩa là một số đường đi nặng sẽ kết hợp để tạo thành một đường đi duy nhất, nhưng tất cả các đường đi nặng sẽ vẫn không giao nhau. Vẫn đảm bảo rằng đi xuống một cạnh nhẹ làm giảm kích thước cây con xuống một nửa hoặc ít hơn.
- Thay vì xây dựng segment tree trên mọi đường đi nặng, một segment tree duy nhất có thể được sử dụng với các đoạn không giao nhau được phân bổ cho mỗi đường đi nặng.
- Đã đề cập rằng việc trả lời các truy vấn đòi hỏi phải tính toán LCA. Trong khi LCA có thể được tính toán riêng biệt, cũng có thể tích hợp tính toán LCA trong quá trình trả lời các truy vấn.
Để thực hiện phân rã heavy-light:
vector<int> parent, depth, heavy, head, pos;
int cur_pos;
int dfs(int v, vector<vector<int>> const& adj) {
int size = 1;
int max_c_size = 0;
for (int c : adj[v]) {
if (c != parent[v]) {
parent[c] = v, depth[c] = depth[v] + 1;
int c_size = dfs(c, adj);
size += c_size;
if (c_size > max_c_size)
max_c_size = c_size, heavy[v] = c;
}
}
return size;
}
void decompose(int v, int h, vector<vector<int>> const& adj) {
head[v] = h, pos[v] = cur_pos++;
if (heavy[v] != -1)
decompose(heavy[v], h, adj);
for (int c : adj[v]) {
if (c != parent[v] && c != heavy[v])
decompose(c, c, adj);
}
}
void init(vector<vector<int>> const& adj) {
int n = adj.size();
parent = vector<int>(n);
depth = vector<int>(n);
heavy = vector<int>(n, -1);
head = vector<int>(n);
pos = vector<int>(n);
cur_pos = 0;
dfs(0, adj);
decompose(0, 0, adj);
}
init, và việc phân rã được thực hiện giả sử đỉnh 0 là gốc.
Hàm dfs được sử dụng để tính toán heavy[v], con ở đầu kia của cạnh nặng từ v, cho mỗi đỉnh v. Ngoài ra dfs cũng lưu trữ cha và độ sâu của mỗi đỉnh, sẽ hữu ích sau này trong các truy vấn.
Hàm decompose gán cho mỗi đỉnh v các giá trị head[v] và pos[v], tương ứng là đầu của đường đi nặng mà v thuộc về và vị trí của v trên segment tree duy nhất bao gồm tất cả các đỉnh.
Để trả lời các truy vấn trên các đường đi, ví dụ truy vấn tối đa được thảo luận, chúng ta có thể làm một cái gì đó như thế này:
int query(int a, int b) {
int res = 0;
for (; head[a] != head[b]; b = parent[head[b]]) {
if (depth[head[a]] > depth[head[b]])
swap(a, b);
int cur_heavy_path_max = segment_tree_query(pos[head[b]], pos[b]);
res = max(res, cur_heavy_path_max);
}
if (depth[a] > depth[b])
swap(a, b);
int last_heavy_path_max = segment_tree_query(pos[a], pos[b]);
res = max(res, last_heavy_path_max);
return res;
}