DIY Tree
Contest: Deltix Round, Summer 2021 (open for everyone, rated, Div. 1 + Div. 2)
Difficulty rating: 3300
Tags: graphs, greedy, math, probabilities

William really likes puzzle kits. For one of his birthdays, his friends gifted him a complete undirected edge-weighted graph consisting of $$$n$$$ vertices.

He wants to build a spanning tree of this graph, such that for the first $$$k$$$ vertices the following condition is satisfied: the degree of a vertex with index $$$i$$$ does not exceed $$$d_i$$$. Vertices from $$$k + 1$$$ to $$$n$$$ may have any degree.

William wants you to find the minimum weight of a spanning tree that satisfies all the conditions.

A spanning tree is a subset of edges of a graph that forms a tree on all $$$n$$$ vertices of the graph. The weight of a spanning tree is defined as the sum of weights of all the edges included in a spanning tree.

Input format:
The first line of input contains two integers $$$n$$$, $$$k$$$ ($$$2 \leq n \leq 50$$$, $$$1 \leq k \leq min(n - 1, 5)$$$).

The second line contains $$$k$$$ integers $$$d_1, d_2, \ldots, d_k$$$ ($$$1 \leq d_i \leq n$$$).

The $$$i$$$-th of the next $$$n - 1$$$ lines contains $$$n - i$$$ integers $$$w_{i,i+1}, w_{i,i+2}, \ldots, w_{i,n}$$$ ($$$1 \leq w_{i,j} \leq 100$$$): weights of edges $$$(i,i+1),(i,i+2),\ldots,(i,n)$$$.

Output format:
Print one integer: the minimum weight of a spanning tree under given degree constraints for the first $$$k$$$ vertices.

Constraints:
Time limit: 6.0 s
Memory limit: 256.0 MB

Example input:
10 5
5 3 4 2 1
29 49 33 12 55 15 32 62 37
61 26 15 58 15 22 8 58
37 16 9 39 20 14 58
10 15 40 3 19 55
53 13 37 44 52
23 59 58 4
69 80 29
89 28
48

Example output:
95

Editorial:
Let's call the first $$$k$$$ vertices special.
First of all, let's note that the number of different forests on $$$5$$$ vertices is at most $$$300$$$. It means that we can try all of them, one by one, as the set of all edges of the answer with both endpoints being the special vertices.
Let $$$T$$$ be the set of chosen edges with both endpoints being the special vertices. With fixed $$$T$$$, only edges with zero or one endpoint at special vertices are left. From now on, we will only consider subsets of these edges.
We will introduce two matroids:
• Matroid $$$A$$$ is defined as follows: A set of edges $$$E$$$ is independent for matroid $$$A$$$, if the set $$$E \cup T$$$ has no cycles. $$$A$$$ is a matroid, because:  Deleting edges produces no cycles, so if $$$F$$$ is a superset of $$$E$$$ and $$$F$$$ is independent, then $$$E$$$ is also independent. If $$$|F| > |E|$$$, $$$F$$$ is independent and $$$E$$$ is independent, then from the graphic matroid there should be an edge in $$$T \cup F$$$ that connects connected components in $$$T \cup E$$$. This edge can't be from $$$T$$$, so there is an element $$$x \in F$$$, s. t. $$$E \cup \{x\}$$$ is also independent.
• Deleting edges produces no cycles, so if $$$F$$$ is a superset of $$$E$$$ and $$$F$$$ is independent, then $$$E$$$ is also independent.
• If $$$|F| > |E|$$$, $$$F$$$ is independent and $$$E$$$ is independent, then from the graphic matroid there should be an edge in $$$T \cup F$$$ that connects connected components in $$$T \cup E$$$. This edge can't be from $$$T$$$, so there is an element $$$x \in F$$$, s. t. $$$E \cup \{x\}$$$ is also independent.
• Matroid $$$B$$$ is defined as follows. A set of edges $$$E$$$ is independent for matroid $$$B$$$, if in the set $$$E \cup T$$$ degrees of vertices $$$[1,2,\ldots,k]$$$ don't exceed $$$[d_1,d_2,\ldots,d_k]$$$, respectively. $$$B$$$ is a matroid, because: Deleting edges decreases degrees, so if $$$F$$$ is a superset of $$$E$$$ and $$$F$$$ is independent, then $$$E$$$ is also independent. If $$$|F| > |E|$$$, $$$F$$$ is independent and $$$E$$$ is independent, then one of the following statements is true. Either there is an edge with zero endpoints at special vertices in $$$F \setminus E$$$, and we can add it to $$$E$$$ preserving independence. Or there is some vertex $$$v \in \{1,2,\ldots,k\}$$$ that has larger degree in $$$F$$$ than in $$$E$$$, and we can take one of adjacent edges that are present in $$$F \setminus E$$$ and add it to $$$E$$$. Thus, there is an element $$$x \in F$$$, s. t. $$$E \cup \{x\}$$$ is also independent.Let's find the minimum weight base $$$E$$$ in the intersection of matroids $$$A$$$ and $$$B$$$. If it has enough edges, we can relax the answer with the total weight of edges in $$$E \cup T$$$.Also note that we are only interested in edges from $$$\{1, \ldots, k\} \times \{k+1,\ldots,n\}$$$ and in the MST of edges from $$$\{k+1,\ldots,n\}$$$, so we only have $$$O(nk)$$$ edges we need to consider.Total complexity is $$$O(\mathrm{exp}(k) \cdot \mathrm{poly}(n)))$$$, and it will easily fit into TL if your solution is efficient enough.
• Deleting edges decreases degrees, so if $$$F$$$ is a superset of $$$E$$$ and $$$F$$$ is independent, then $$$E$$$ is also independent.
• If $$$|F| > |E|$$$, $$$F$$$ is independent and $$$E$$$ is independent, then one of the following statements is true. Either there is an edge with zero endpoints at special vertices in $$$F \setminus E$$$, and we can add it to $$$E$$$ preserving independence. Or there is some vertex $$$v \in \{1,2,\ldots,k\}$$$ that has larger degree in $$$F$$$ than in $$$E$$$, and we can take one of adjacent edges that are present in $$$F \setminus E$$$ and add it to $$$E$$$. Thus, there is an element $$$x \in F$$$, s. t. $$$E \cup \{x\}$$$ is also independent.