Star MST
Contest: Educational Codeforces Round 125 (Rated for Div. 2)
Difficulty rating: 2200
Tags: combinatorics, dp, graph matchings, math

In this problem, we will consider complete undirected graphs consisting of $$$n$$$ vertices with weighted edges. The weight of each edge is an integer from $$$1$$$ to $$$k$$$.

An undirected graph is considered beautiful if the sum of weights of all edges incident to vertex $$$1$$$ is equal to the weight of MST in the graph. MST is the minimum spanning tree — a tree consisting of $$$n-1$$$ edges of the graph, which connects all $$$n$$$ vertices and has the minimum sum of weights among all such trees; the weight of MST is the sum of weights of all edges in it.

Calculate the number of complete beautiful graphs having exactly $$$n$$$ vertices and the weights of edges from $$$1$$$ to $$$k$$$. Since the answer might be large, print it modulo $$$998244353$$$.

Input format:
The only line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 250$$$; $$$1 \le k \le 250$$$).

Output format:
Print one integer — the number of complete beautiful graphs having exactly $$$n$$$ vertices and the weights of edges from $$$1$$$ to $$$k$$$. Since the answer might be large, print it modulo $$$998244353$$$.

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

Example input:
3 2

Example output:
5

Example input:
4 4

Example output:
571

Editorial:
Let the weight of the edge between the vertex $$$x$$$ to the vertex $$$y$$$ be $$$w_{x,y}$$$.
Suppose there exists a pair of vertices $$$x$$$ and $$$y$$$ (with indices greater than $$$2$$$) such that $$$w_{x,y} < w_{1,x}$$$ or $$$w_{x,y} < w_{1,y}$$$. Then, if we choose the spanning tree with all vertices connected to $$$1$$$, it won't be an MST: we can remove either the edge $$$(1,x)$$$ or the edge $$$(1,y)$$$, add the edge $$$(x,y)$$$ instead, and the cost of the spanning tree will decrease. So, we should have $$$w_{x,y} \ge \max(w_{1,x}, w_{1,y})$$$ for every pair $$$(x, y)$$$.
It can be shown that this condition is not only necessary, but sufficient as well: if for every pair $$$(x, y)$$$ the condition $$$w_{x,y} \ge \max(w_{1,x}, w_{1,y})$$$ holds, the MST can't have the weight less than $$$\sum \limits_{i=2}^{n} w_{1,i}$$$. We can prove this by induction (suppose that $$$w_{1,2} \le w_{1,3} \le \ldots \le w_{1,n}$$$ for simplicity):
• in the spanning tree, there should be at least one edge incident to vertex $$$n$$$, and its weight is at least $$$w_{1,n}$$$;
• there should be at least two edges incident to vertices $$$n$$$ and $$$n-1$$$, and their weights are at least $$$w_{1,n-1} + w_{1,n}$$$;
• ...;
• there should be at least $$$n-1$$$ edges incident to vertices from $$$2$$$ to $$$n$$$, and their weights are at least $$$\sum \limits_{i=2}^{n} w_{1,i}$$$.
Okay, now let's show how to calculate the number of such graphs. We can run the following dynamic programming: let $$$dp_{i,j}$$$ be the number of graphs where we have already connected $$$i$$$ vertices to the vertex $$$1$$$, and the maximum weight we have used is $$$j$$$. We start with $$$dp_{0,0}$$$, and for each transition from $$$dp_{i,j}$$$, we will iterate on the number of vertices we connect to the vertex $$$1$$$ with edges with weight $$$(j+1)$$$ (let the number of those vertices be $$$t$$$), choose them with a binomial coefficient $$$\frac{(n-1-i)!}{t!(n-1-i-t)!}$$$, and also choose the weights for the edges that connect one of the chosen vertices with one of the vertices already connected to $$$1$$$ (since for each of those edges, we know that their weights should be in $$$[j+1,k]$$$) — so, we need to multiply the value in transition by $$$(k-j)^e$$$, where $$$e$$$ is the number of such edges.
Implementing this dynamic programming can be done in $$$O(n^2k)$$$ or $$$O(n^2 k \log n)$$$, both are sufficient.