Tóm tắt: Cho cây ~N~ đỉnh và ~N - 1~ cạnh có trọng số, ở đỉnh ~i~ có số ~A_i~. Tính tổng ~f(u, v) = s(u, v) \times dist(u, v)~ với mọi ~1 \le u < v \le N~, với ~s(u, v)~ là tổng các ước chung của ~A_u~ và ~A_v~.

Subtask 1 (11p): ~N \leq 300~.

Ta DFS ở từng đỉnh, khi đến mỗi đỉnh ta tính ~s(u, v)~ trong ~O(\sqrt{X})~. ĐPT tổng thể là ~O(N^2 \sqrt{MAX_A})~.

Hoặc có thể dùng Floyd - Warshall ~O(N^3)~ rồi duyệt từng cặp đỉnh =))))

Subtask 2 (16p): ~N \le 2000~

Nhận xét: Hiển nhiên ~s(u, v) = s(gcd(A_u, A_v)))~.

Tối ưu từ Subtask 1, ta có thể tính trước các ~s(x)~ vào một mảng, sau đó có thể tìm trong ~O(1)~ khi đang DFS.

ĐPT: ~O(N^2 + MAX_A \sqrt{MAX_A})~ hoặc ~O(N^2 + MAX_A \log \log MAX_A)~ tùy vào cách cài đặt.

Subtask 3 (27p): ~A_1 = A_2 = \ldots = A_N~

Vì các ~A_i~ bằng nhau nên ta không cần quan tâm việc tính ~s(u, v)~ (~s(u, v)~ lúc này sẽ luôn là tổng số ước của ~A_i~ bất kì). Khi đó chúng ta có thể tính riêng tổng ~dist(u, v)~ sau khi nhóm ~s(u, v)~ ra ngoài, sau đó đáp án sẽ là tích của hai số này.

Bài toán tính tổng khoảng cách giữa các cặp đỉnh trên cây là một bài toán cổ điển có thể giải bằng nhiều cách, vì vậy xin được nhường lại cho người đọc.

Gợi ý: Xét một cạnh trên cây, có bao nhiêu cách chọn ~u, v~ sao cho đường đi từ ~u~ đến ~v~ phải đi qua cạnh này? Nếu tính được số cách chọn, ta có thể dễ dàng tính được đóng góp của cạnh này vào ~\sum_u \sum_v dist(u, v)~.

ĐPT: ~O(N)~.

Subtask 4 (27p): ~u_i + 1 = v_i~

Dễ thấy cây trong trường hợp này có dạng đường thẳng.

Nhận xét: Một số bất kì từ ~1~ đến ~15 \times 10^4~ có tối đa khoảng ~150~ ước.

Từ nhận xét trên, ta có thể gộp các đỉnh cùng có ước là ~x~ vào một tập, rồi tính tổng khoảng cách giữa các cặp đỉnh trong tập đó. Vì các số không có quá ~150~ ước nên tổng số đỉnh ta xét sẽ không quá ~150 \times N~.

Việc tính tổng khoảng cách có thể dùng cách từ Subtask 3. Chú ý là ta phải dựng một đồ thị mới cho từng tập đỉnh, nhưng vì cây có dạng đường thẳng nên việc dựng đồ thị cũng khá dễ do ta chỉ cần dựng cạnh giữa các đỉnh liên tiếp.

ĐPT: ~O(150 \times N)~.

Subtask 5 (19p): Không có giới hạn gì thêm

Để giải quyết Subtask này, các bạn cần biết kiến thức về cây ảo. Ở dưới là một số blog rất hay các bạn có thể tham khảo:

• HackMD - Virtual/Auxiliary Tree (Cây ảo) - Zero_OP
• Codeforces Blog - Tutorial on Virtual/Auxiliary Trees - radoslav11

Từ Subtask 4, vì cây không còn là đường thẳng nữa nên ta sẽ dựng cây ảo cho từng tập đỉnh, sau đó làm như Subtask 3.

Việc dựng cây ảo mất ~O(n \log n)~ và ta có tối đa ~150 \times N~ đỉnh cần xét, vậy ĐPT của thuật toán là ~O(150 \times N \times \log N)~.