Hint 是 \(n\) 个 \([0,1]\) 之间均匀随机分布的数的第 \(k\) 小值的期望为 \(\frac{k}{n+1}\)，证明可见这篇博客。
考虑 Kruskal 求最小生成树的过程。从小到大加入每条边，当加入第 \(i\) 一条边时整张图联通了，那么 \(w_i\) 就是生成树上边权最大值。
这启示我们钦定一个边集 \(S\)，包含了前 \(|S|\) 小的边权，加入第 \(|S|\) 条边时整张图刚好联通。由提示知道此时 \(S\) 对答案的贡献为 \(\frac{|S|}{m+1}\)。考虑统计大小为 \(i\) 的符合 \(|S|=i\) 的方案数，除以总方案 \(\dbinom{m}{i}\) 即可得到概率。
难搞的限制在于加入第 \(i\) 条边时恰好联通，考虑容斥，转化成加入第 \(i\) 条边 \(S_i\) 前不连通的方案数减去加入第 \(i\) 条边后不连通的方案数。于是概率就变成了加入 \(S_i\) 前不连通的概率减去加入 \(S_i\) 后不连通的概率。
于是只需要求出加入 \(S_i\) 后不连通的方案数。考虑 dp，设 \(f_{T,i}\) 为考虑点集 \(T\)，其中连了 \(i\) 条边，点集内不连通的方案数；为了方便转移，维护 \(g_{T,i}\) 为考虑点集 \(T\)，连 \(i\) 条边，联通的方案数。显然有 \(f_{T,i}+g_{T,i}=\dbinom{d_T}{i}\)，\(d_T\) 表示点集 \(T\) 导出子图中边的个数，即 \(|E(G(T))|\)。
考虑转移，由于不能联通，枚举一个连通块 \(T'\subsetneqq T\) 及其内部边数，连通块外任意连边，那么：
但是这样做有个问题，对于对于不同的连通块可能会算重。所以在 \(T'\) 中钦定一个点 \(k\in T\)，\(k\in T'\)。
答案就是 \(\large\sum\limits_{k=1}^{m+1}\frac{k}{m+1}\left(\dfrac{f_{U,k-1}}{\dbinom{m}{k-1}}-\dfrac{f_{U,k}}{\dbinom{m}{k}}\right)\)，\(U\) 为全集。可以化简但没必要，复杂度 \(O(3^nm^2)\)。
很奇怪，我不开 O2 可以过，开了过不了。