Phương Nam có $N$ khu vực hành chính, được đánh số từ $1$ đến $N$, được kết nối liên thông bởi $N - 1$ con đường tạo thành dạng cây trong lý thuyết đồ thị. Mỗi khu vực tương ứng với một đỉnh của cây, mỗi con đường tương ứng với một cạnh của cây. Nhắc lại, cây là một đồ thị vô hướng, liên thông và không có chu trình. Mỗi khu vực người ta gán cho một giá trị biểu thị mức độ phát triển khu vực đó, khu vực thứ $i$ có có giá trị $A_i$.

Nhằm quy hoạch phát triển các khu vực một cách hiệu quả, người ta đánh giá một cụm $S$ các khu vực liên thông nhau thông qua các con đường nối giữa chúng trong cụm đó bởi một độ hiệu quả. Giá trị độ hiệu quả này được tính bằng hiệu của giá trị lớn nhất trong số các giá trị khu vực thuộc $S$ và giá trị nhỏ nhất trong số các giá trị khu vực thuộc $S$. Nói cách khác, với một cụm liên thông $S$, giá trị của $S$ là $max_{u∈S} A_u - min_{u∈S} A_u$.

Người ta muốn chia toàn bộ $N$ khu vực thành các cụm khu vực riêng biệt, mỗi cụm bao gồm một hoặc nhiều khu vực liên thông nhau bởi các con đường nối các khu vực trong cụm đó và đánh giá độ hiệu quả trên mỗi cụm. Tổng độ hiệu quả của một cách chia như vậy được tính bằng tổng giá trị của các cụm liên thông trong cách chia đó.

Yêu cầu: Hãy tìm cách chia toàn bộ $N$ khu vực thành các cụm có tổng độ hiệu quả lớn nhất.