Subtask 1

Ta sẽ duyệt từng cạnh để thay đổi. Với mỗi cạnh thay đổi, ta chọn ~2~ đỉnh của ~2~ thành phần liên thông mới và nối lại. Từ đó tính tổng khoảng cách ứng với cách thay đổi đó. ĐPT: ~O(N^4)~ hoặc ~O(N^4 \times log(N))~.

Subtask 2, 3, 4 đều dùng nhận xét quan trọng: Với mỗi cạnh bị thay đổi, số lần đi qua cạnh mới luôn giữ nguyên, vì vậy ~2~ đỉnh ~u, v~ mới được chọn để nối vào cần đảm bảo tổng đường đi từ đỉnh trong thành phần liên thông của u đến u và tổng đường đi từ đỉnh trong thành phần liên thông của v đến v là bé nhất.

Subtask 2

Duyệt cạnh để xóa, sau đó với mỗi thành phần liên thông, dfs từ tất cả các đỉnh để tìm đỉnh tối ưu nhất. ĐPT: ~O(N^3)~.

Subtask 3

Với đồ thị đường thẳng và trọng số bằng ~1~, khi ta xóa ~1~ cạnh, ta sẽ xác định được ~2~ đỉnh cần nối là ~2~ đỉnh nằm giữa của ~2~ đoạn bị chia ra. Sử dụng mảng cộng dồn hoặc hai con trỏ để tính chi phí. ĐPT: ~O(N^2)~.

Subtask 4

Cải tiến từ sub2, sau khi xóa ~1~ cạnh, ta có thể tính chi phí tối ưu nhất bằng cách sử dụng reroot dp. Giả sử khi ta có chi phí tại đỉnh ~a~, ta có thể tính chi phí của các đỉnh ~b~ kề với ~a~ như sau: ~cost_b = cost_a - sz_b * w + (S - sz_b) * w~ (với ~cost_x~ là chi phí tại ~x~, ~sz_x~ là số node trong cây con gốc ~x~, ~w~ là trọng số cạnh ~(a, b)~, ~S~ là tổng số đỉnh trong thành phần liên thông đó). ĐPT: ~O(N^2)~.