Problem Statement
This problem has a non-standard time limit: 7 seconds.
You have a complete undirected graph with N labeled vertices. You have to assign a positive integer weight less than or equal to K to each of its N*(N-1)/2 edges.
Count all those assignments of weights such that the graph has a unique minimum spanning tree. Return the count modulo a prime number M .
Definition
- Class:
- UniqueMST
- Method:
- count
- Parameters:
- int, int, int
- Returns:
- int
- Method signature:
- int count(int N, int K, int M)
- (be sure your method is public)
Notes
- A tree is a connected graph with no cycles.
- A spanning subgraph of G is a subgraph that contains all vertices of the original graph G.
- A spanning tree of G is a spanning subgraph of G that is a tree.
- A minimum spanning tree of G is a spanning tree such that the sum of its edge weights is the smallest among all spanning trees of G.
Constraints
- N will be between 2 and 50, inclusive.
- K will be between 1 and 10 9 , inclusive.
- M will be a prime number between max(N, K) + 1 and 10 9 , inclusive.
Examples
2
5
29
Returns: 5
With just two vertices and a single edge between them the MST is always unique.3
3
11
Returns: 4
As there are three vertices, the MST is unique if and only if the edge with maximum weight is unique. This happens for the following assignments of weights: There are 3 assignments where the edge weights are 1, 1, 2 in some order. There are 3 assignments where the edge weights are 1, 1, 3 in some order. There are 6 assignments where the edge weights are 1, 2, 3 in some order. There are 3 assignments where the edge weights are 2, 2, 3 in some order. Thus, the total number of good assignments of weights is 3 + 3 + 6 + 3 = 15 and the returned answer is (15 mod 11) = 4.7
2
998244353
Returns: 16807
For N = 7 and K = 2 the MST is unique if and only if all edges with weight 1 form exactly a spanning tree.