Subtask 1 (17% số điểm): n, M ≤ 5000.

Xây dựng trước mảng \(2\) chiều \(dis[i][j]\) là khoảng cách từ đỉnh \(i\) tới đỉnh \(j\) bằng. Duyệt \(x\) tăng dần từ \(1\) tới \(m\) và cập nhật tổng khoảng cách từ một đỉnh tới \(x\) đỉnh đặc biệt đầu tiên, sau đó chọn đáp án nhỏ nhất.

Độ phức tạp: \(O(n × n + q × n).\)

Subtask 2 (19% số điểm): Cây có dạng đường thẳng.

Ta xem cây như một mảng một chiều, nhận thấy với một tập đỉnh cho trước thì đỉnh có tổng khoảng cách bé nhất sẽ là trung vị của tập đỉnh này. Ta sẽ dùng chặt nhị phân và cấu trúc dữ liệu để tìm trung vị đồng thời tính tổng khoảng cách.

Độ phức tạp: \(O(q × log_2(n)\)

Subtask 3 (20% số điểm): m = 3 trong mỗi truy vấn.

Với mỗi tập các điểm đặc biệt, ta nhận thấy đỉnh \(G\) sẽ là một trong các đỉnh đó hoặc là LCA của \(2\) đỉnh đặc biệt nào đó. Ở \(subtask\) này vì \(m\) nhỏ nên ta hoàn toàn có thể duyệt hết các đỉnh tiềm năng và tính khoảng cách.

Độ phức tạp: \(O(q × m^3).\)

Subtask 4 (21% số điểm): w = 1 trong mỗi cạnh.

Rút ra từ \(subtask 2\), ta có thể có nhận xét với một tập \(x\) đỉnh đặc biệt thì đỉnh \(G\) chính là \(centroid\) của tập đỉnh đó (tức là khi cắt đỉnh đó khỏi cây thì không có nhánh nào chứa quá \(x/2\) đỉnh đặc biệt).

Từ đây ta có thể xét \(x\) lần lượt từ \(1\) đến \(m\) và duy trì centroid và tổng khoảng cách cho \(x\) đỉnh đặc biệt đầu tiên. Giả sử centroid cho \(x − 1\) đỉnh đầu tiên là \(C\), nếu ta thêm đỉnh \(a_x\) thì centroid mới sẽ nằm trên đường đi từ \(C\) tới \(a_x\).

Ta thấy \(C\) sẽ không còn là trọng tâm chỉ khi nhánh chứa \(a_x\) nếu cắt \(C\) khỏi cây chứa quá \(x/2\) đỉnh đặc biệt, khi đó trọng tâm mới sẽ là đỉnh đầu tiên trên đường đi từ \(C\) đến \(a_x\) mà làm giảm số đỉnh trong nhánh chứa \(a_x\) đi.

Khi đó ta sẽ dùng chặt nhị phân và cấu trúc dữ liệu để tìm ra đỉnh đầu tiên đó, đồng thời cập nhật tổng khoảng cách.

Độ phức tạp: \(O(n × log_2(n) + q × log_2^2(n))\).

Subtask 5 (23% số điểm): Không có ràng buộc gì thêm.

Gọi \(R\) là tổ tiên chung gần nhất của \(C\) và \(a_i\), ta sẽ tìm trọng tâm mới trên lần lượt đường đi từ \(C\) đến \(R\) và \(R\) đến \(a_i\). Giả sử ta xét trên đường đi từ \(C\) đến \(R\), khi đó trọng tâm mới sẽ là tổ tiên của \(C\) và đồng thời làm giảm nhánh chứa \(a_i\), hay nói cách khác số lượng đỉnh đặc biệt trên cây con gốc của đỉnh này sẽ khác với cây con của \(C\). Để tìm đỉnh đầu tiên thỏa mãn ta chỉ cần dùng thứ tự DFS và cấu trúc dữ liệu Segment Tree để kiểm soát liệu cây con của đỉnh ta chặt nhị phân tới có được thêm đỉnh đặc biệt nào không.

Đường đi từ \(R\) tới \(a_i\) ta cũng làm tương tự.

Độ phức tạp: \(O((n + q) × log_2(n)).\)