题解

思路

设星形树中边 $(1,i)$ 的权值为 $x_i$。根据最小生成树的环性质，这棵星形树是一棵 MST 当且仅当对每条非树边 $(i,j)$ 都有

$$w_{i,j}\ge \max(x_i,x_j).$$

因此固定所有 $x_i$ 后，边 $(i,j)$ 有 $k-\max(x_i,x_j)+1$ 种合法权值。

做法

子任务 1 可枚举完全图的全部边权，用 Kruskal 算法检查星形树是否为 MST。

子任务 2 枚举 $n-1$ 条星形边的权值，并将各非树边的合法取值数相乘，复杂度 $O(k^{n-1}n^2)$。

满分做法按权值从小到大处理。设已有 $p$ 个顶点的星形边权已确定，当前权值 $v$ 再选 $c$ 个顶点时，有 $\binom{n-1-p}{c}$ 种选法。新确定最大值为 $v$ 的非树边数是

$$pc+\binom c2,$$

它们各有 $k-v+1$ 种权值。因此转移为

$$dp'_{p+c}\mathrel{+}=dp_p\binom{n-1-p}{c}(k-v+1)^{pc+\binom c2}.$$

复杂度

满分算法时间复杂度 $O(kn^2)$，空间复杂度 $O(n^2)$。