CF1556H DIY Tree

William 非常喜欢拼图套装。在他的某个生日，他的朋友们送给了他一个包含 $n$ 个顶点的完全无向带权图。 他想要在这个图中构建一棵生成树，使得对于前 $k$ 个顶点满足以下条件：编号为 $i$ 的顶点的度数不超过 $d_i$。编号从 $k+1$ 到 $n$ 的顶点度数没有限制。 William 希望你找到一棵满足所有条件的生成树的最小权值。 生成树是图中边的一个子集，能够在所有 $n$ 个顶点上形成一棵树。生成树的权值定义为生成树中所有边的权值之和。

输入的第一行包含两个整数 $n$ 和 $k$（$2 \leq n \leq 50$，$1 \leq k \leq \min(n-1, 5)$）。 第二行包含 $k$ 个整数 $d_1, d_2, \ldots, d_k$（$1 \leq d_i \leq n$）。 接下来的 $n-1$ 行中，第 $i$ 行包含 $n-i$ 个整数 $w_{i,i+1}, w_{i,i+2}, \ldots, w_{i,n}$（$1 \leq w_{i,j} \leq 100$）：分别表示边 $(i,i+1),(i,i+2),\ldots,(i,n)$ 的权值。

输出一个整数：满足给定度数限制条件下的最小生成树的权值。

由 ChatGPT 4.1 翻译