XJOI200730 题解
A
求最小生成树边权期望。
“保证距离值相同的道路数小于 30”，显然可以用矩阵树定理。
根据期望的可加性，整棵树的期望 = 每条边的期望 之和。考虑最小生成树的性质（具体可见 JSOI2008-最小生成树计数），我们分别处理不同长度的边。而每条边的概率是：（包含这条边的生成树个数）/（总生成树个数）。分开做就可以过了，虽然时间复杂度是不对的。
然而还有一个神仙做法：flying2018大佬博客
C
为什么没往数据结构想呢。。。要反思，这一看就很线段树嘛
忽略 limit 的限制——最左的位置可以二分。
max值是单调不增的。
线段树维护每一个 f[i] 和 max{…}。