tag: dynamic programming, trie, small to large, centroid decomposition.

Đầu tiên, cho mình xin lỗi vì đề bài ngu của LKT.

Tóm tắt ngắn gọn lại đề bài: Cho một cây gồm ~N~ đỉnh, độ tuyệt vời của cặp đỉnh ~(u, v)~ là tổng xor của đường đi đơn từ ~u~ đến ~v~. Bạn cần tìm độ tuyệt vời lớn nhất của mọi cặp ~(u, v)~ và đếm xem có bao nhiêu cặp có độ tuyệt vời bằng độ tuyệt vời lớn nhất đấy.

Subtask 1

Làm gì cũng được.

ĐPT: ~O(hio)~

Subtask 2

Với mỗi đỉnh ~u~ ta tiến hành dfs hoặc bfs để tính độ đẹp của đỉnh ~u~ tới mọi đỉnh ~v~ khác, sau đó tính đáp án theo đề bài.

ĐPT: ~O(N^2)~

Subtask 3

Vì ~A_i \leq 1~, nên độ tuyệt vời lớn nhất của đồ thị chính là ~1~. Nên nếu không tồn tại một đường đi có độ tuyệt vời là ~1~ thì độ tuyệt vời của đồ thị sẽ bằng ~0~ và số cặp thỏa mãn sẽ là ~N^2~. Nếu có tồn tại, chúng ta sẽ tiến hành đếm số đường đi có độ tuyệt vời là ~1~ như sau:

Gọi ~s(u, v)~ là độ đẹp của cặp ~(u, v)~, ~f_u~ là số đỉnh con ~v~ sao cho ~s(u, v) = 1~, ~g_u~ là số đỉnh con ~v~ sao cho ~s(u, v) = 0~.

Ta dễ dàng tính ~f_u~ và ~g_u~ bằng công thức sau:

• Nếu ~A_u = 1~:

  • ~f_u = 1 + \sum{g_v}~

  • ~g_u = \sum{f_v}~

• Nếu ~A_u = 0~:

  • ~f_u = \sum{f_v}~

  • ~g_u = 1 + \sum{g_v}~

Trong đó, ~v~ là đỉnh con trực tiếp của ~u~.

Khi có được ~f_u~ và ~g_u~, ta có thể dễ dàng tính được đáp án (mời bạn đọc tự tính do mình lười).

ĐPT: ~O(N)~

Subtask 4

Gọi ~f_{u, i}~ là số đỉnh con ~v~ sao cho ~s(u, v) = i~.

Ta dễ dàng tính được ~f_{u, i}~ bằng công thức sau: ~f_{u, i} = \sum{f_{v, j}}~ với mọi ~j, v~ thỏa mản ~j \oplus A_u = i~ và ~v~ là đỉnh con trực tiếp của ~u~ (Tất nhiên, ~f_{u, A_u}~ được cộng thêm ~1~).

(Mình quên mất phần sau nên mình mời bạn đọc làm tiếp subtask này).

ĐPT: ~O(N \times 32^2)~

Subtask 5

Để giải quyết được subtask cuối cùng, chúng ta cần giải quyết được bài toán dễ hơn:

"Cho ~1~ dãy gồm ~N~ số không âm, tìm tổng xor lớn nhất của một đoạn liên tiếp của mảng này".

Duyệt trâu thông thường sẽ có ĐPT là ~O(N^2)~, sẽ không qua được giới hạn của bàn toán. Để tối ưu hóa, chúng ta để ý rằng tổng xor của đoạn ~[l...r]~ là ~pref_r \oplus pref_{l - 1}~ với ~pref_i~ là tổng xor của đoạn ~[1...i]~. Ta cố định ~pref_r~, với mỗi ~r~ ~(1 \leq r \leq N)~ ta cần tìm ~l~ ~(l \leq r)~ sao cho ~pref_r \oplus pref_{l - 1}~ lớn nhất. Ta duy trì một trie lưu các giá trị ~pref_1, pref_2, ..., pref_r~, rồi xét từ bit lớn nhất tới bit nhỏ nhất, mỗi lần như vậy ta kiểm tra xem có tồn tại ~pref_i~ sao cho bit lớn thứ ~j~ ~\oplus~ bit lớn thứ ~j~ của ~pref_r~ có bằng ~1~ hay không. Với cách làm này, ta giảm ĐPT từ ~O(N^2)~ xuống ~O(N \times log_2(\max(A_i)))~. VNOI wiki cũng có phần nói về bài này Link.

Trở về bài toán chính, với mỗi đỉnh ~u~ chúng ta có thể lưu một trie chứa các giá trị ~s(u, v)~. Để gộp trie một cách hiệu quả, ta sử dụng kỹ thuật small to large. Trong quá trình gộp, ta lấy toàn bộ giá trị ở trie nhỏ hơn, rồi coi thử xem giá trị xor lớn nhất với trie lớn hơn là bao nhiêu bằng tư duy trên.

ĐPT: ~O(N \times log_2(\max(A_i))^2)~

Tài liệu tham khảo

• Trie

• Small to Large

• That xor problem