Nguồn: Code Festival 2016 - Elimination Tournament Round 1 - Problem A https://atcoder.jp/contests/cf16-tournament-round1-open/tasks/asaporo_c
Trước hết, với phương án đặt trạm điện tại hai thành phố A và B, ta có thể xem như chỉ đặt trạm điện tại thành phố A, và có thể xây dựng đường dây điện nối giữa A và B với chi phí 0. Từ đó, ta nghĩ ra được thuật toán cho hai subtask đầu tiên: bổ sung thêm cạnh (A, B, 0) và tìm cây khung cực tiểu (minimum spanning tree) của đồ thị M + 1 cạnh bằng thuật toán Kruskal. Thuật toán trên có độ phức tạp O(QM log(N + M)).
Để cải tiến thuật toán trên, ta cần hiểu bản chất của thuật toán Kruskal. Trước hết, ta sẽ tìm cây khung cực tiểu T của đồ thị M cạnh. Nhận xét rằng, khi bổ sung một cạnh có trọng số 0 giữa hai đỉnh A và B, cạnh này chắc chắn sẽ nằm trong cây khung tối thiểu. Khi đó, đường đi giữa A và B trong T và cạnh (A, B) sẽ tạo thành một chu trình. Do thuật toán Kruskal xét các cạnh theo trọng số từ nhỏ đến lớn, cạnh có trọng số lớn nhất trên đường đi giữa A và B sẽ bị bỏ ra khỏi cây khung cực tiểu.
Do đó, gọi W là tổng trọng số của các cạnh trong T, maxW(u, v) là cạnh có trọng số lớn nhất trên đường đi giữa u và v trên T. Khi đó, với truy vấn i, đáp án sẽ là W − maxW(A_i, B_i).
Đến đây, ta đã có lời giải độ phức tạp O(M log(N + M) + QN), đủ để vượt qua subtask 3. Để được trọn vẹn điểm bài này, ta cần thực hiện việc tính toán trước maxW(u, v) với mọi cặp (u, v) trong O(N^2) bằng cách DFS từ từng đỉnh. Khi đó, mỗi truy vấn có thể được trả lời trong O(1).
Độ phức tạp: O(M log(N + M) + N^2 + Q).