Để làm được bài này, trước hết bạn cần biết về LCA và Heavy Light Decomposition (HLD).
## Đưa về bài toán trên cây
**Nhận xét.** Trong một trie, với hai xâu $s, t$ lần lượt ứng với hai đỉnh $u, v$ trên trie thì đỉnh ứng với tiền tố chung dài nhất của $s$ và $t$ trên trie sẽ ứng với đỉnh $lca(u,v)$.
Vì bằng các dựng trie ứng với $n$ xâu nhập vào, gọi $\texttt{wpos}[u]$ là đỉnh ứng với xâu thứ $u$ trên trie, mỗi truy vấn $(l, r, k)$ sẽ quy về tính tổng:
$$
\sum_{i = l}^r\texttt{depth}(lca(\texttt{wpos}[k], \texttt{wpos}[i]))
$$
## Tính chất của tổng độ sâu các LCA
Xét một cây bất kỳ và đỉnh $x$ cố định, giả sử ta cần tính tổng:
$$
\sum_{i = l}^r \texttt{depth}(lca(x, i))
$$
Gọi $\texttt{cnt}(u, l, r)$ là số lượng đỉnh có chỉ số thuộc đoạn $[l, r]$ trong cây con gốc $u$. Khi đó tổng trên bằng tổng các $\texttt{cnt}(u, l, r)$ với mọi $u$ là đỉnh nằm trên đường đi từ $x$ đến gốc và không tính gốc. (Giải thích thế này hơi khó hiểu nên bạn đọc nên vẽ cây ra để dễ hình dung).
## Xử lí truy vấn
Ta xử dụng kỹ thuật offline query bằng cách tận dụng ý tưởng của mảng cộng dồn: $[l, r] = [1, r] - [1, l - 1]$. Qua đó, mỗi truy vấn $[l, r]$ có thể tách thành hai truy vấn $[1, l - 1]$ và $[1, r]$ nên ta chỉ cần xử lí các truy vấn dạng $[1, x]$.
Dựa vào nhật xét trên, ta có ý tưởng: Sắp xếp các truy vấn tăng dần theo $x$, mỗi khi cập nhật $x$ thì tăng các đỉnh thuộc đường đi từ $u$ đến gốc lên $1$ đơn vị. Sau đó với mỗi truy vấn ở đỉnh $x$ chỉ cần in ra tổng đường đi từ gốc đến $x$ (chú ý trừ đi giá trị của gốc).
Để thực hiện ý tưởng trên ta cần một cấu trúc dữ liệu giúp cập nhật, truy vấn đường đi hiệu quả. Với HLD, mỗi thao tác được thực nên trong $O(log^2 n)$ dẫn đến thuật toán có độ phức tạp $O((n + q)\log ^2n)$ cộng thêm chi phí dựng trie là $O(\sum |S_i|)$, ta có thuật toán đủ nhanh để AC bài toán!!!.
Ngoài ra nếu sử dụng Link-cut Tree có thể giảm độ phức tạp mỗi truy vấn xuống $O(\log n)$ nhưng cách này không phù hợp nếu không được sử dụng template.
chithanhnguyen
Created at
3 likes