P3343 [ZJOI2015] 地震后的幻想乡
如果得知\(f_{U,k}\)表示选\(k\)条边把\(U\)联通的概率，我们钦定这\(k\)条边就是前\(k\)小条边，那么\(f_{U,k}-f_{U,k-1}\)，就是恰好在第\(k\)条边的时候联通的概率，也就是最小生成树的最大边就是第\(k\)个边。由于都在\([0,1]\)中取值，所以第\(k\)小的期望就是\(\frac{k}{m+1}\),那么如果求出了\(f_{U,k}\)求出来就好了。那么容斥，枚举编号最小的点所在的连通块在哪里，然后这个连通块要联通，利用前面的信息，然后剩下的点就是随意，但是不能和这个连通块有连边。
总结：必须算出的是概率，不能是方案数，因为概率相当于相对于所有的排列的比例，但是方案数只考虑前\(k\)个，没有考虑后面边的方案，所以就不对了。求法就是可以先算方案数，然后让\(\frac{f_{U,k}}{\binom{m}{k}}\)就行了。
总结：这个容斥的方法比较经典，就是选一个特定的点，枚举其所在的连通块，然后考虑其他点的联通不连通