MST with half the edges the maximum weight
If the answer is "yes", then there is an easy algorithm: just compute any MST and report the number of edges with weight $C$.  If they all have the same number of edges with weight $C$, then the particular MST you compute won't change the answer.

So now you want to know whether the answer is yes.  To see that it is, observe that each MST is constructed by running the greedy algorithm on a specific linear extension of the partial order induced by the weights.  In your case, the edges $E$ partitioned into sets $E_{&lt;C}$ and $E_C$, and every edge in $E_{&lt;C}$ comes before any edge in $E_C$ for all of these linear extensions.  That tells you that every MST is made of a spanning forest $F$ on the subgraph induced by $E_{&lt;C}$ and some edges from $E_C$; since all the choices for $F$ have the same size, we are done.