Bessie có một đồ thị vô hướng đơn với các đỉnh được đánh số \(1\dots N\) (\(2\le N\le 750\)). Cô sinh một thứ tự duyệt theo chiều sâu (DFS) của đồ thị bằng cách gọi hàm \(\texttt{dfs}(1)\), được định nghĩa bởi đoạn mã C++ sau. Mỗi danh sách kề (\(\texttt{adj}[i]\) với mọi \(1\le i\le N\)) có thể được hoán vị tùy ý trước khi bắt đầu duyệt theo chiều sâu, nên một đồ thị có thể có nhiều thứ tự DFS khả dĩ.

vector<bool> vis(N + 1);
vector<vector<int>> adj(N + 1);  // adjacency list
vector<int> dfs_order;

void dfs(int x) {
    if (vis[x]) return;
    vis[x] = true;
    dfs_order.push_back(x);
    for (int y : adj[x]) dfs(y);
}

Bạn được cho trạng thái ban đầu của đồ thị cũng như chi phí để thay đổi trạng thái của mỗi cạnh. Cụ thể, với mọi cặp đỉnh \((i,j)\) thỏa mãn \(1\le i<j\le N\), bạn được cho một số nguyên \(a_{i,j}\) (\(0<|a_{i,j}|\le 1000\)) sao cho:

• Nếu \(a_{i,j}>0\), cạnh \((i,j)\) hiện không có trong đồ thị và có thể được thêm vào với chi phí \(a_{i,j}\).
• Nếu \(a_{i,j}<0\), cạnh \((i,j)\) hiện có trong đồ thị và có thể được xóa với chi phí \(-a_{i,j}\).

Hãy xác định tổng chi phí nhỏ nhất để thay đổi đồ thị sao cho \([1,2\dots,N]\) là một thứ tự DFS khả dĩ.

Dữ liệu vào

Dòng đầu tiên chứa \(N\).

Tiếp theo là \(N-1\) dòng. Dòng thứ \(j-1\) chứa \(a_{1,j}, a_{2,j}, \dots, a_{j-1,j}\), cách nhau bởi dấu cách.

Dữ liệu ra

Chi phí nhỏ nhất để thay đổi đồ thị sao cho \([1,2,\dots, N]\) là một thứ tự DFS khả dĩ.

Ví dụ

4
1
2 3
40 6 11

10

5
-1
10 -2
10 -7 10
-6 -4 -5 10

5

4
-1
-2 300
4 -5 6

9

Phân nhóm

• Inputs 4-9: Mọi \(a_{i,j}>0\).
• Inputs 10-16: \(N\le 50\).
• Inputs 17-23: Không có ràng buộc bổ sung.

Nguồn

USACO 2025 January Contest, Platinum — DFS Order

Đề bài: https://usaco.org/index.php?page=viewproblem2&cpid=1476

Tác giả đề: Benjamin Qi