Editorial for Cây khung nhỏ nhất

Việc áp dụng trực tiếp thuật toán tìm cây khung nhỏ nhất vào bài toán này sẽ dẫn đến việc cần kiểm tra tổng cộng $N^2$ ~N^2~ cạnh, vì vậy ta cần xác định các cạnh nối quan trọng, từ đó chỉ cần tìm cây khung nhỏ nhất dựa trên các cạnh này. Bài toán có thể được giải quyết bằng kỹ thuật Chia để trị.

Ta cần xác định các cạnh quan trọng giữa các đỉnh thuộc đoạn $[L,R]$ ~[L,R]~. Chia đoạn $[L,R]$ ~[L,R]~ thành hai phần $[L,M]$ ~[L,M]~ và $[M+1,R]$ ~[M+1,R]~. Sau khi xác định các cạnh quan trọng ở từng phần, ta cần xác định các cạnh quan trọng nối từ một đỉnh thuộc phần thứ nhất với một đỉnh thuộc phần thứ hai.

Chi phí giữa hai đỉnh $i$ ~i~ $(L \le i \le M)$ ~(L \le i \le M)~ và $j$ ~j~ $(M+1 \le j \le R)$ ~(M+1 \le j \le R)~ có thể được viết lại thành $f(i)+g(j)$ ~f(i)+g(j)~, với $f(i)=A_i-D \times i$ ~f(i)=A_i-D \times i~ và $g(j)=A_j+D \times j$ ~g(j)=A_j+D \times j~.

Gọi $i_0$ ~i_0~ và $j_0$ ~j_0~ lần lượt là vị trí đạt giá trị nhỏ nhất của $f$ ~f~ và $g$ ~g~. Khi đó, cạnh nối hai đỉnh $i-j$ ~i-j~ được xem là một cạnh quan trọng khi và chỉ khi $i=i_0$ ~i=i_0~ hoặc $j=j_0$ ~j=j_0~. Trong trường hợp $i \neq i_0$ ~i \neq i_0~ và $j \neq j_0$ ~j \neq j_0~, ba cạnh nối $i-j_0$ ~i-j_0~, $j_0-i_0$ ~j_0-i_0~ và $i_0-j$ ~i_0-j~ sẽ có trọng số nhỏ hơn so với cạnh $i-j$ ~i-j~, từ đó cạnh $i-j$ ~i-j~ không thể là một cạnh của cây khung nhỏ nhất. Vì vậy, có tổng cộng $N.log(N)$ ~N.log(N)~ cạnh quan trọng.