Lời giải đầy đủ tại đây. Slides chữa bài của VNOI tại đây.

Tóm tắt đề bài

Cho một cây gồm ~N~ đỉnh, đỉnh thứ ~i~ có trọng số là ~A_i~. Bạn cần phải giải quyết ~Q~ truy vấn, với truy vấn thứ ~j~:

• Gồm ba số nguyên dương ~x_j,y_j,w_j~. Xét mọi đỉnh ~v~ trên đường đi ngắn nhất từ ~x_j~ tới ~y_j~, cập nhật ~A_v:=A_v\ mod\ w_j~.
• Yêu cầu xác định giá trị của ~\sum_{i=1}^N A_i\ mod\ j~.

Giới hạn và subtask

• ~1\le N,Q\le 2\times 10^5~
• ~0\le A_i\le 2\times 10^5~ với mọi ~i~ từ ~1~ đến ~N~
• Các cạnh ~(u,v)\ (1\le u,v\le N,u\ne v)~ trong ~N-1~ cạnh thỏa mãn tạo thành cây
• ~1\le x_j,y_j\le N~ với mọi ~j~ từ ~1~ đến ~Q~
• ~1\le w_j\le N~ với mọi ~j~ từ ~1~ đến ~Q~

~\dagger~: Tồn tại cạnh nối giữa hai đỉnh ~i~ và ~i+1~ với mọi ~i~ từ ~1~ đến ~N-1~.

Subtask 1: ~N,Q\le 5000~

Subtask này đơn giản chỉ là làm theo yêu cầu đề bài.

Với mỗi truy vấn, ta duyệt qua tất cả đỉnh trên đường đi ngắn nhất từ ~x_j~ đến ~y_j~ và thực hiện cập nhật, sau đó for trâu để lấy đáp án.

Việc duyệt đỉnh có thể thực hiện bằng DFS hoặc BFS (cần cái đặt khéo léo một xí do hằng số cao).

Độ phức tạp: ~O(Q\times N)~.

Subtask 2: ~A_i\le 2~ với mọi ~i~ từ ~1~ đến ~N~; ~(\dagger)~

Với điều kiện ~(\dagger)~, bài toán trên cây giờ chỉ còn là bài toán trên dãy số, và mỗi truy vấn là một truy vấn đoạn. Tuy nhiên vì đề không nói gì về thông tin ~x_j\le y_j~ nên khi thực hiện truy vấn phải đổi giá trị của chúng trong trường hợp cần thiết để thuận tiện xử lý.

Nhận xét 1: Nếu ~a\ge b~ thì ~a\ mod\ b<a~, ngược lại ~a\ mod\ b=a~.</p>

Ta có thể thấy khi thực hiện phép modulo, giá trị của ~A_i~ luôn giảm dần. Nếu trong mỗi truy vấn, ta chỉ quan tâm những đỉnh mà chắc chắn sẽ bị thay đổi thì số thao tác cập nhật lại tối đa sẽ là ~2N~ (do giới hạn đặc biệt của subtask là ~A_i\le 2~).

Do ~A_i\le 2~, ta có thể tạo hai CTDL lưu trữ vị trí của các số ~1,2~ trên dãy ~A~ (ta không cần xét các số ~0~ vì giá trị của các phần tử đó không bao giờ thay đổi nữa). Khi xét truy vấn ~(x_j,y_j,w_j)\ (u_j\le v_j)~, ta tìm vị trí của các phần tử lớn hơn hoặc bằng ~w_j~ trong đoạn ~[x_j;y_j]~ và cập nhật lại dựa trên các CTDL đã tạo.

Để trả lời truy vấn, ta áp dụng đếm phân phối để duy trì số lượng số ~0,1,2~ trong dãy và lấy kết quả trong ~O(1)~.

Độ phức tạp: ~O\left((N+Q)\times log(N)\right)~ (có thể khác tùy vào CTDL sử dụng).

Subtask 3: ~x_j=y_j~ với mọi ~j~ từ ~1~ đến ~Q~; ~(\dagger)~

Định nghĩa giá trị ~M=2\times 10^5~.

Do mỗi truy vấn, ta chỉ cập nhật lại một đỉnh nên ta không cần phải để ý vấn đề cập nhật nhanh. Tuy nhiên, ta cần phải quan tâm tới vấn đề thứ hai của bài toán: Tính kết quả nhanh.

Ta xét bài toán con đơn giản hơn: Giả sử dãy ~A~ luôn không đổi sau các truy vấn, và ta cần xác định các giá trị ~\sum_{i=1}^n A_i\ mod\ j~ với mọi ~j~ từ ~1~ đến ~Q~.

Ta có một nhận xét như sau:

Nhận xét 2: ~a\ mod\ b=a-\lfloor\frac{a}b \rfloor\times b~.

Từ nhận xét trên, ta có thể đưa bài toán về việc tính ~\sum_{i=1}^n A_i-\left(\sum_{i=1}^n \lfloor\frac{A_i}j\rfloor \right)\times j~.

Xét phép toán ~\sum_{i=1}^n \lfloor\frac{A_i}j\rfloor~, ta có thể xét mọi khoảng ~[j\times t,j\times (t+1))~ ~(j\times t\le M)~ và đếm số lượng phần tử có giá trị trong khoảng đó rồi nhân với ~t~ để cộng vào tổng. Việc này có thể giải quyết bằng prefix sum.

Với mỗi số ~j~, ta cần khoảng ~\frac{M}j~ lần lấy tổng như trên. Vì thế nên số lần lấy tổng với mọi ~j~ từ ~1~ đến ~M~ sẽ bằng ~\sum_{i=1}^{M} \frac{M}i\approx M\times log(M)~ (đây là harmonic sum, các bạn có thể tìm hiểu trên mạng để hiểu rõ hơn).

Quay trở lại bài toán, thay vì dùng prefix sum, ta tạo một fenwick tree để quản lý số lần xuất hiện của các phần tử trong dãy. Khi xét truy vấn thứ ~j~, ta cập nhật lại mảng tần số trong ~O(log(M))~ và lấy tổng ~\frac{M}j~ lần.

Độ phức tạp: ~O\left(M\times log^2(M)\right)~.

Subtask 4: ~(\dagger)~

Ta có thêm một nhận xét về phép ~mod~ như sau:

Nhận xét 3: Với mỗi phần tử ~A_i~, số lần thay đổi tối đa sẽ xấp xỉ ~log(A_i)~.

Chứng minh: Xét phép ~A_i\ mod\ w\ (A_i\ge w)~. Có ~2~ trường hợp như sau:

• Nếu ~\lfloor \frac{A_i}2\rfloor<w\le A_i\rightarrow A_i\ mod\ w=A_i-w\le \lfloor \frac{A_i}2\rfloor~.</li>
• Nếu ~1\le w\le \lfloor \frac{A_i}2\rfloor\rightarrow A_i\ mod\ w<w\le \lfloor \frac{A_i}2\rfloor~.</li>

Như vậy sau mỗi lần cập nhật ~A_i:=A_i\ mod\ w~, giá trị này sẽ luôn nhỏ hơn hoặc bằng một nửa. Suy ra điều cần chứng minh.

Từ nhận xét trên, ta có thể thấy số lần thay đổi tối đa của các phần tử trong dãy ~A~ chỉ xấp xỉ ~N\times log(M)~.

Để cập nhật nhanh, ta dùng một segment tree để quản lý giá trị và vị trí của phần tử lớn nhất trong đoạn. Khi xét truy vấn ~(x_j,y_j,w_j)\ (x_j\le y_j)~:

• Chọn phần tử lớn nhất trong đoạn ~[x_j;y_j]~. Nếu phần tử đó lớn hơn hoặc bằng ~w_j~, thực hiện cập nhật lại phần tử đó. Nếu không thì ta biết đoạn ~[x_j;y_j]~ đã hết phần tử cần phải cập nhật.
• Mỗi khi cập nhật một phần tử, ta cũng cập nhật lại mảng tần số trên fenwick tree.
• Thực hiện thao tác trên đến khi không còn phần tử nào lớn hơn hoặc bằng ~w_j~ trong đoạn nữa.

Tất cả thao tác trên segment tree/fenwick tree đã nói ở trên đều có độ phức tạp là ~O(log(N))~.

Độ phức tạp: ~O\left(N\times log(N)\times log(M)+M\times log^2(M)\right)~.

Subtask 5: Không có ràng buộc gì thêm

Để có thể giải được subtask cuối, ta vẫn sử dụng ý tưởng của subtask 4, đồng thời áp dụng thuật toán Heavy-Light Decomposition để có thể giải được trên cây.

Độ phức tạp: ~O\left(N\times log(N)\times log(M)+M\times log^2(M)\right)~.