Subtask 1: Có ~30\%~ số test ứng với ~30\%~ số điểm của bài thoả mãn: ~N \le 20~.

Duyệt tất cả các trường hợp xóa cạnh có thể xảy ra, với mỗi trường hợp ta sử dụng BFS/DFS để tính toán giá trị cho từng thành phần liên thông như đề yêu cầu.

Độ phức tạp ~O(2N \times N)~.

Subtask 2: ~30\%~ số test khác ứng với ~30\%~ số điểm của bài thoả mãn: ~N \le 2000~, và tất cả các đỉnh có bậc không quá ~2~.

Bài toán có thể đưa về bài toán trên dãy, và ta có thể sử dụng quy hoạch động để giải. Cụ thể gọi ~dp[i]~ là đáp án tối ưu nếu dùng ~i~ đỉnh đầu tiên. Khi đó:

~dp[i] = \underset{1 \le j < i}{max}(dp[j − 1] + \underset{j \le k \le i}{max}(a[k]) − \underset{j \le k \le i}{min}(a[k])); dp[0] = 0~

Công thức này hoàn toàn có thể tính được trong O(N^2)

Subtask 3: ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: Tất cả các đỉnh có bậc không quá ~2~. Nhận xét rằng nếu một dãy có phần tử nhỏ nhất (hoặc lớn nhất) không nằm ở đầu hoặc cuối dãy, ta có thể chia dãy đó ra làm hai mà không làm kết quả tồi đi. Ví dụ ta có ~(1, 7, 3, 4) = 6~ trong khi ~(1, 7) + (3, 4) = 7~. Do đó phải tồn tại cách chia tối ưu mà giá trị lớn nhất và nhỏ nhất đều nằm ở hai đầu của dãy.

Sử dụng quy hoạch động ~dp[i][1/2/3]~ là giá trị tối ưu nếu ta xét đến vị trí ~i~ và:

1. đã chọn vị trí đầu tiên của dãy là vị trí nhỏ nhất
2. đã chọn vị trí đầu tiên của dãy là vị trí lớn nhất
3. đã chọn xong cho cả đầu và cuối dãy, và i cũng là vị trí kết thúc một dãy con.

Khi đó:

• ~dp[0][1] = dp[0][2] = −\infty, dp[0][3] = 0~
• ~dp[i][1] = max(dp[i − 1][1], dp[i − 1][3] − a[i])~
• ~dp[i][2] = max(dp[i − 1][2], dp[i − 1][3] + a[i])~
• ~dp[i][3] = max(dp[i − 1][3], dp[i − 1][1] + a[i], dp[i − 1][2] − a[i])~ Lưu ý rằng ta không cần quan tâm một vị trí đã chọn có thực sự là nhỏ nhất hoặc lớn nhất khi được chọn hay không, mà ta chỉ cần giả định điều đó xảy ra và hàm quy hoạch động sẽ tự thực hiện một cách tối ưu.

Độ phức tạp ~O(N)~.

Subtask 4: ~20\%~ số test còn lại ứng với ~20\%~ số điểm của bài: Không có ràng buộc gì thêm. Tương tự ở trên, nhận xét rằng chỉ có một đường đi từ phần tử lớn nhất đến phần tử nhỏ nhất là quan trọng, trong khi các phần còn lại có thể cắt ra mà không làm kết quả tồi đi. Do đó tồn tại phương án tối ưu mà mỗi thành phần liên thông là một đường đi. Ta đặt ~dp[i][1/2/3/4]~ là giá trị tối ưu nếu chỉ xét cây con gốc ~i~ và thành phần chứa đỉnh ~i~:

1. chưa chọn ra phần tử lớn nhất và phần tử nhỏ nhất.
2. đã chọn ra phần tử nhỏ nhất.
3. đã chọn ra phần tử lớn nhất.
4. đã chọn ra cả phần tử lớn nhất và phần tử nhỏ nhất.

Với mỗi đỉnh u, ta duyệt từng đỉnh con ~v~ và thực hiện gộp cây con ~v~ với cây con gốc ~u~. Cụ thể:

• ~nxt[0] = dp[u][0] + dp[v][3]~
• ~nxt[1] = max(dp[u][1] + dp[v][3], dp[u][0] + dp[v][1])~
• ~nxt[2] = max(dp[u][2] + dp[v][3], dp[u][0] + dp[v][2])~
• ~nxt[3] = max{dp[u][0] + dp[v][3], dp[u][3] + dp[v][3], dp[u][1] + dp[v][2], dp[u][2] + dp[v][1]}~

Trong đó ~nxt[x]~ là giá trị của ~dp[u][x]~ sau khi gộp.

Độ phức tạp: ~O(N)~.