#1658. 「USACO 2025.1 Platinum」DFS Order

Bessie 有一个无向简单图，结点编号为 （）。她通过调用函数 生成该图的一个深度优先搜索（depth-first search，DFS）序，函数由以下 C++ 代码定义。各邻接表（对于所有 的 ）在开始深度优先搜索之前可以任意排列，因此一个图可以有多个可能的 DFS 序。

vector<bool> vis(N + 1);
vector<vector<int>> adj(N + 1);  // 邻接表
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);
}

给定图的初始状态以及修改每条边状态的代价。具体地说，对于每对满足 的结点 ，给定一个整数 （），其中

• 如果 ，则边 当前不在图中，可以以代价 添加。
• 如果 ，则边 当前在图中，可以以代价 移除。

求使得 成为一个可能的 DFS 序的最小总代价。

输入的第一行包含 。

以下 行，第 行包含 ，以空格分隔。

输出使得 成为一个可能的 DFS 序的最小总代价。

输入 #1

4
1
2 3
40 6 11

输出 #1

10

输入 #2

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

输出 #2

5

输入 #3

4
-1
-2 300
4 -5 6

输出 #3

9

样例 1 解释：

初始时，图中没有边。可以添加边 可以得到总代价 。现在图有两个可能的 DFS 序：。

样例 2 解释：

初始时，图中包含边 。移除边 可以得到总代价 。

样例 3 解释：

初始时，图中包含边 。移除边 并且添加边 可以得到总代价 。

• 测试点 ：所有 。
• 测试点 ：。
• 测试点 ：没有额外限制。