AT_arc167_c [ARC167C] MST on Line++

首先遇到这种题先不要慌，先拆贡献。

考察一个权值为 \(a_i\) 的边会被 MST 包含多少次，因为我们确定了 \(p\)，所以 \(a\) 的顺序就没有关系了，我们先将 \(a\) 排序，钦定某一种边权出现次数很难做，但是我们如果钦定不大于某种边权的出现次数为 \(f_i\)，那么就有了转机了（这实际上是一个经典 trick）。

先设出来，问题会被转化为满足 \(|j - i| \le k\)，且 \(a_j \le a_i\)，此时能选的边尽量选，问最后不成环的方案数。\(a_j > a_i\) 的点显然是不能连边的，随便考虑可以阶乘计算，然后 \(a_j \le a_i\) 的点也可以置换一下，也乘上个阶乘的系数。

然后一个比较重要的观察是，MST 可能有多种方案，但是，我们一定可以找出一种最优的方案，使得 \(a\) 从小到大相邻有一条边，知道这一步了，组合计数就并不困难了。

感觉这种题还是要看结构的特殊性。