Dành cho các bạn thích đọc paper (:wink:): https://ics.uci.edu/~eppstein/pubs/Epp-TR-92-04.pdf
Ý tưởng để giải quyết bài này khá giống với Offline Dynamic Connectivity,
mỗi cạnh $e = (u_e, v_e, w_e)$ sẽ tồn tại trong một khoảng thời gian $[l_e, r_e)$ ($0 \le l_e \lt r_e \le q$).
Chúng ta sẽ chia để trị trên thời gian truy vấn $[0, q)$, và để việc xử lý được hiệu quả
ta cần tìm cách giới hạn số lượng cạnh cần xử lý ở mỗi khoảng thời gian $[l, r)$.
Để thực hiện được điều đó, chúng ta sẽ thực hiện 2 thủ tục sau:
- Tìm thành phần liên thông được nối bởi các cạnh nhất định thuộc mọi MST trong
khoảng $[l, r)$ và nén mỗi thành phần lại thành một đỉnh.
- Tìm các cạnh nhất định không thuộc MST trong khoảng $[l, r)$ và xóa chúng.
### Nén đồ thị
Khi duyệt đến các cạnh tồn tại trong khoảng $[l, r)$, ta sẽ xét đến 2 loại cạnh:
1. Một phần (hoặc toàn bộ) cạnh nằm trong $[l, r)$ ($l \lt l_e \text{ or } r_e \lt r$)
2. $[l, r)$ nằm hoàn toàn trong $[l_e, r_e)$ ($l_e \le l \text { and } r \le r_e$)
Ta tạm thời gán cho các cạnh loại 1 trọng số $-\infty$, gọi đồ thị tạm thời là
$G'$ và MST của nó là $T'$. Để ý rằng sau khi chạy Kruskal trên $G'$ thì các
cạnh loại 2 nằm trong $T'$ luôn nằm trong mọi MST trong khoảng $[l, r)$.
Do khi ta tăng trọng số các cạnh loại 1 thì vị trí của nó sau khi sắp xếp theo
trọng số sẽ chỉ tăng lên, không ảnh hưởng đến các cạnh loại 2.
Các cạnh loại 2 được nói đến ở trên tạo thành các thành phần liên thông và chúng ta có
thể nén chúng lại mà không lo ảnh hưởng đến MST của các đoạn con của $[l, r)$.
Gọi $m_1$ là số cạnh loại 1 đang xét, do trong $T'$ chỉ có tối đa $m_1$ cạnh loại 1,
số thành phần liên thông khi xóa chúng khỏi $T'$ sẽ là $m_1+1$. Vậy đồ thị được nén
$G_d$ sẽ chỉ có tối đa $m_1+1$ đỉnh.
### Loại bỏ các cạnh không cần thiết
Hiện tại, $G_d$ chỉ có tối đa $m_1+1$ đỉnh, ta sẽ loại bỏ các cạnh loại 2 nhất
định không thuộc MST nào trong $[l, r)$ bằng cách chạy Kruskal trên các cạnh loại 2.
Sau đó ta bỏ các cạnh loại 2 không được sử dụng trong thuật toán (vì nếu thêm các
cạnh loại 1 vào thì khả năng chọn chúng càng thấp hơn). Đồ thị mới này sẽ là một
rừng khung nhỏ nhất (minimum spanning forest), vì ta chỉ xét các cạnh loại 2 và
không đảm bảo toàn bộ đỉnh đã được nối. Số lượng cạnh tối đa sẽ là $m_1$.
Ngoài ra thay vì sort các cạnh mỗi lần đệ quy để chạy Kruskal, ta chỉ cần sort
chúng ngay trước khi chia để trị, và khi loại bỏ các cạnh, cần giữ vị trí tương đối
của chúng là được, giảm độ phức tạp của Kruskal xuống còn $O(n+(m+q)\alpha(n))$.
Vậy độ phức tạp thời gian tổng thể là $O((m+q)\log(q)\alpha(n))$.
### Pseudocode
```cpp
// Xử lý khoảng [l, r) với danh sách cạnh edges, số đỉnh là n, trọng số của MST hiện tại là m
solve(l, r, edges, n, weight) {
xóa các cạnh nằm ngoài khoảng [l, r)
reset dsu1, dsu2
for (e in edges)
if (type(e) == 1) dsu1.merge(e.u, e.v)
for (e in edges)
if (type(e) == 2)
if (dsu1.merge(e.u, e.v)) weight += e.w, dsu2.merge(u, v)
reset dsu1
id = 0
for (v in [0, n)) if (v == dsu2.find(v)) label[v] = id++
for (e in edges) {
e.u = label[dsu2.find(e.u)], e.v = label[dsu2.find(e.v)]
if (type(e) == 2)
if (!dsu1.merge(e.u, e.v)) e.r = -1 // xóa cạnh e
}
m = (l + r) / 2
solve(l, m, edges, id, weight)
solve(m, r, edges, id, weight)
}
```
imsuck
Created at
1 likes