For a subset $$$A \subset \begin{Bmatrix}1, \ldots, n\end{Bmatrix}$$$ we introduce the notation

for convenience. First, note that $$$\mathcal{I}$$$ always contains $$$\varnothing,$$$ since $$$s(\varnothing) = 0$$$. As a result we cannot violate condition $$$1.$$$ Similarly, it is impossible to violate condition $$$2,$$$ since for $$$A \supset B$$$ we have

and $$$s(A \setminus B) \geq 0$$$ by non-negativity of the weights $$$w_i.$$$

We say a set $$$A$$$ is constrained if $$$s(A) \leq c$$$ and for all $$$x \not \in A,$$$ $$$s(A \cup \begin{Bmatrix}x\end{Bmatrix}) \geq c.$$$ Clearly if we can find constrained sets $$$A, B$$$ with $$$|A| \neq |B|$$$ then we have a contradiction to the third condition.

Consider the sets $$$M_{\min}$$$ and $$$M_{\max}$$$ constructed as follows:

For $$$M_{\min},$$$ iterate through the indices $$$\begin{Bmatrix}1,\ldots, n\end{Bmatrix}$$$ in non-decreasing order of $$$w_i.$$$ At each index, if adding it to the set keeps $$$s(M_{\min})$$$ at most $$$c,$$$ then add it to $$$M_{\min}.$$$ For $$$M_{\max},$$$ perform the same algorithm with the indices initially in non-increasing order of weights.

It is well known that $$$M_{\min}$$$ is the constrained set with the maximum size and $$$M_{\max}$$$ is the constrained set of minimum size. The proof is quite simple and thus is left as an exercise.

If $$$|M_{\min}| \gt |M_{\max}|$$$ then we are done. Otherwise, we know that all constrained sets have the same size; call this $$$k.$$$

We now make the following claim: If $$$|A| \gt |B|$$$ are sets which contradict property $$$3$$$, then there exist sets $$$C \supset A$$$ and $$$D \supset B$$$ such that $$$|C| = k$$$ and $$$|D| = k - 1$$$ which also contradict this property. We split the proof of this claim into two lemmas.

Lemma 1. If $$$|A| \lt k$$$ then we can construct $$$|C| = k.$$$

Proof: Since $$$|B| \lt |A| \lt k$$$ neither of these sets are constrained. Then there exist indices $$$i,j$$$ which can be added to $$$B$$$ and $$$A$$$ respectively. We can add $$$x = \text{argmin}_{u \in \begin{Bmatrix}i,j\end{Bmatrix}} w_u$$$ to both sets. The proof is completed by induction.

Lemma 2. If $$$|A| - |B| \gt 1$$$ then we can construct $$$|C| - |D| = 1.$$$

Proof: Since $$$|B| \lt k - 1$$$ there exists some element which can be added to $$$B.$$$ If this element is not in $$$A$$$ then it does not affect the validity of our contradiction. If it is in $$$A,$$$ then our pair $$$A,B$$$ is not valid by definition of property $$$3$$$.

Finally, note that two sets $$$A,B$$$ form a valid pair if and only if the minimum weight of an index in $$$A \setminus B$$$ cannot be added to $$$B.$$$ In fact, if a pair $$$A,B$$$ contradicts property $$$3,$$$ then there exists a pair $$$C,D$$$ which also contradicts the property, such that the minimum weight element in $$$C$$$ does not occur in $$$D.$$$ The proof of this claim is very similar to that of the lemmas above, and the reader is encouraged to work out the details.

So now what we are looking for is a pair of sets $$$A,B$$$, such that the minimum element of $$$A$$$ is large enough that we cannot add it to $$$B$$$. What we will do is construct the sets $$$A,B$$$ with the greatest minimum and smallest allowable final element, respectively, since if a pair $$$A,B$$$ exists then this pair is also valid.

The first set can be constructed by iterating over suffixes of the weights in sorted order and taking $$$M_{\min}$$$ of the shortest suffix which satisfies $$$M_{\min} = k.$$$ The second set is simply $$$M_{\max} \setminus {u},$$$ where $$$u$$$ is the element of minimum weight. We can construct these sets and check if they form a valid contradiction. If they do not, then the set of solutions is a matroid.

We use divide and conquer, using halfplane partitions passing through points to split the plane into several convex regions. The algorithm is as follows:

• Identify the highest degree point $$$p$$$ in the current set; let the degree of $$$p$$$ be $$$k$$$. Sort all other points by angle around this point. Use angular sweepline to maintain a sliding window of 180 degrees around $$$p$$$. There are $$$N$$$ such windows that matter (one for each line passing through any point and $$$p$$$).
• Let $$$S$$$ be the set of points in the window and $$$k = |S|$$$. Then, if $$$\sum_{s \in S} deg[s] \lt 2k \lt \sum_{s \in S} deg[s] + deg[p]$$$, we can partition the problem along a line passing through $$$p$$$. For now, I claim that a partition satisfying this inequality always exists (*).
• Subproblem 1: $$$S$$$ plus point $$$p$$$, but in this subproblem assign $$$deg[p] = 2k - \sum_{s \in S} deg[s]$$$
• Subproblem 2: All remaining points plus point $$$p$$$, but in this subproblem assign $$$deg[p]=\sum_{s\in S}deg[s]+deg[p]-2k$$$.
• In the sample input, an example of this partition is as follows (given as a list of {node, degree} pairs):
  • $$$(1, 1), (2, 1), (5, 2)$$$
  • $$$(2, 1), (4, 3), (6, 1), (7, 1), (5, 2)$$$.
• The partition is through node $$$5$$$ which originally has degree 4, and we assign 2 "degrees" to each partition $$$P$$$ so that $$$\sum_{s \in P} deg[s] = 2|P| - 2$$$, and it is possible to make a tree.
• Base case: 2 nodes of degree 1, which we connect with an edge.

This subdivision assigns the exact amount of "degrees" required to construct a tree in both partitions, which are connected through $$$p$$$. Furthermore, edges from one partition cannot intersect the other because the partitioned regions are convex and disjoint. The divide-and-conquer tree in this case is a binary tree with $$$n-1$$$ leaves, so we perform $$$n-1$$$ partition operations. Each partition takes $$$O(n \log n)$$$ time for sorting and $$$O(n)$$$ for sweepline, so overall this algorithm runs in $$$O(n^2 \log n)$$$. time.

Proof of claim (*):

The inequality can be simplified to $$$0 \lt 2k - \sum_{s \in S} deg[s] \lt deg[p]$$$. We can treat $$$2k - \sum_{s \in S} deg[s]$$$ as a periodic function $$$f(\theta)$$$ with respect to the angle of the partition line.

Consider an arbitrary partition line at angle $$$\theta$$$. If $$$0 \lt f(\theta) \lt deg[p]$$$ then we are done, otherwise WLOG suppose that $$$f(\theta) \leq 0$$$. Then, the other partition has $$$N - k - 1$$$ points, and has degree sum $$$2(N - 1) - \sum_{s \in S} deg[s] - deg[p]$$$. Then,

Thus, $$$f(\theta + \pi) \geq deg[p]$$$, so at some point $$$f$$$ crosses over from $$$\leq 0$$$ to $$$\geq deg[p]$$$. Additionally, since $$$deg[p] \geq max_{s \in S} deg[s]$$$, the quantity $$$2k - \sum_{s \in S} deg[s]$$$ can only change by $$$\pm (deg[p] - 2)$$$ between consecutive partitions. The interval $$$0 \lt x \lt deg[p]$$$ has size $$$deg[p]-1$$$, therefore if $$$f$$$ crosses over the interval at some point in $$$(\theta, \theta+\pi)$$$, then some partition must fall within the interval.