P11676 [USACO25JAN] DFS Order P

Bessie 有一个无向简单图，结点编号为 $1\dots N$（$2\le N\le 750$）。她通过调用函数 $\texttt{dfs}(1)$ 生成该图的一个深度优先搜索（depth-first search，DFS）序，函数由以下 C++ 代码定义。各邻接表（对于所有 $1\le i\le N$ 的 $\texttt{adj}[i]$）在开始深度优先搜索之前可以任意排列，因此一个图可以有多个可能的 DFS 序。 ```cpp vector vis(N + 1); vector adj(N + 1); // 邻接表 vector 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); } ``` 给定图的初始状态以及修改每条边状态的代价。具体地说，对于每对满足 $1\le i

输入的第一行包含 $N$。 以下 $N-1$ 行，第 $j-1$ 行包含 $a_{1,j}, a_{2,j}, \dots, a_{j-1,j}$，以空格分隔。

输出使得 $[1,2,\dots, N]$ 成为一个可能的 DFS 序的最小总代价。

样例 1 解释： 初始时，图中没有边。可以添加边 $(1,2),(2,3),(2,4)$ 可以得到总代价 $1+3+6$。现在图有两个可能的 DFS 序：$[1,2,3,4],[1,2,4,3]$。 样例 2 解释： 初始时，图中包含边 $(1,2),(2,3),(2,4),(1,5),(2,5),(3,5)$。移除边 $(3,5)$ 可以得到总代价 $5$。 样例 3 解释： 初始时，图中包含边 $(1,2),(1,3),(2,4)$。移除边 $(2,4)$ 并且添加边 $(1,4)$ 可以得到总代价 $5+4=9$。 - 测试点 $4\sim 9$：所有 $a_{i,j}>0$。 - 测试点 $10\sim 16$：$N\le 50$。 - 测试点 $17\sim 23$：没有额外限制。