A. 最小生成树

因为最小生成树上一条非树边的权值必须大于两点的路径上的最大值，

所以最优的策略肯定是将这棵树弄成一个菊花图。

然后考虑把所有的边权按顺序列出来。

如果当前还没有超出 $m$ 条边的限制，那么第 $i$ 条边的贡献就是 $(i-1)*w_i$。

那考虑一个特殊的情况，如果说 $m$ 小到不需要动最后一条边，那最优策略肯定是前面的边权均为 $1$，最后一条边补齐 $s$ 的限制。

否则前 $i-2$ 条边一定已经走满了，令 $p$ 表示需要走最后一条边多少次。

首先仍然构造前面的边权为 $1$，最后的边权为 $s-n+2$。

然后考虑首先进行第一种操作，将前 $n-2$ 条边整体 $+1$，然后给最后一条边 $-(n-2)$。

这样对答案的贡献为 $\frac{(n-2)*(n-3)}{2} - p*(n-2)$，这个玩意是与权值无关的，那就是说最优策略要么不变，要么将操作 1 进行到底。

一个结论是，前 $n-2$ 条边中不会出现三种不同的权值。原因是如果出现第三种不同的权值，因为权值、系数都是递增的。

所以将第三种权值的位置整体 $-1$，第一种权值的位置整体 $+1$，答案一定更优。

那么考虑进行第二种操作，把最后一条边上的权值不断分配给前面的边。

因为要从后往前分配，仍然第 $i$ 次分配造成的贡献，是 $n-i-p$。

那现在的最优决策，要么是一次分配都不进行，要么是不断进行分配。

所以根据上面的讨论，考虑 不进行第一次操作、只进行第一次操作、进行第一次和第二次操作 三种情况就好了。

B. 没有上司的舞会

学习动态 dp 科技，在本题中需要支持动态加边，那就整个 lct 维护动态 dp。

因为不需要换根操作，所以还是很容易实现的，然后这题就无了。

C. 排列问题

第二次做这类题就显得套路了。

首先是显然的二项式反演，问题转化为计数钦定 $k$ 个相同颜色并且相邻的，然后用 $ntt$ 优化一下即可容斥出所有的答案。

关于如何钦定 $k$ 个相同颜色并且相邻的，套路是分别考虑每种颜色划分为若干个连通块，于是相邻的个数就是总数减去连通块数。

然后把不同的颜色整个 EGF 合并起来就结束了。

因为本题保证最终结果不大，直接整个分治就结束了。