Maximize Spanning Tree Stability with Upgrades

Challenge Points: 30

Level: Hard

You are given a graph containing n vertices labeled from 0 to n - 1.
Each edge in the graph is represented as:

[ui, vi, si, musti]

Where:

ui and vi denote endpoints of an undirected edge.
si represents the strength or durability of that edge.
musti determines whether the edge is compulsory:
- If musti = 1, the edge must be used in the spanning tree and cannot be upgraded.
- If musti = 0, the edge is optional and may be upgraded.

You are also given an integer k, which tells you how many total upgrades are allowed.
If an edge is upgradable (i.e., optional), you may double its strength once, consuming one upgrade.

A spanning tree is considered stable based on the smallest edge strength in the tree.
Your objective is to maximize this stability value.

If it is impossible to form a valid spanning tree (for example, the mandatory edges already create a cycle or do not connect all nodes), return -1.

Example 1:

Input: n = 4 edges = [[0,1,5,1],[1,2,2,0],[2,3,4,0],[0,3,1,0]] k = 1

Output: 4

Explanation:

Mandatory edge: [0,1] with strength 5. We can upgrade only one optional edge. The best choice is upgrading [2,3] from 4 → 8. A valid spanning tree is: [0,1] (5), [1,2] (2), [2,3] (8) Minimum = 2 → but we can choose edges [0,1], [2,3], [0,3] upgraded] giving min = 4. Thus max stability = 4.