题意：
给定一个无向图，边权为 \([0,1]\) 之间的随机变量。求图最小生成树最大边权的期望。
\(n\le 10\)。
Soluion:
Meatherm口诏：我都不知道这个东西怎么想出来的
针对这道题，好像正常的方法是转计数然后斯特林反演+dp。但是如果想到概率理论，你就已经赢了
很遗憾，我没想出来
设最大边权随机变量为 \(X\)。其概率分布函数 \(P(t)=P(X\ge t)\)，概率密度函数 \(p(t)\)。
其实这道题已经做完了
易知
\[EX=\int_0^{\infty}P(t)dt=\int_0^1P(t)dt \]接下来考虑这个东西怎么求。首先我们得知道 \(P(t)\) 怎么算。小于 \(t\) 的边不能连通图，那么考虑 \(1\) 所在连通块在使用边权小于 \(t\) 的边不能连通图的概率（这时也就知道了能）。设这个连通块的点集为 \(S(1\in S)\)。类似地，设这个连通块的概率分布函数为 \(P_S(t)\)。
考虑再次枚举此时不连通的"包含 \(1\) 的连通块"，设其为 \(S_0\)。不连通的概率就是枚举每个不同的、不等于他自己的包含 \(1\) 的连通块的连通的概率之和。这样相互独立，覆盖了所有情况。那么可以得到：
\[P_S(t)=\sum_{S_0\subset S\\1\in S_0}(1-t)^{cnt(S_0,\overline{S_0})}(1-P_{S_0}(t)) \]\(cnt\) 是两个点集之间的边计数。这样算的原因：它和它补集之间的点必须不连通（\((1-t)^{cnt(S_0,\overline{S_0})}\)），他自己那里必须连通（\((1-P_{S_0}(t))\)）。
考虑对这个东西积分。
\[\int_0^1P_S(t)dt=\int_0^1\sum_{S_0\subset S\\1\in S_0}(1-t)^{cnt(S_0,\overline{S_0})}(1-P_{S_0}(t))dt\\ =\int_0^1\sum_{S_0\subset S\\1\in S_0}(1-t)^{cnt(S_0,\overline{S_0})}dt-\int_0^1\sum_{S_0\subset S\\1\in S_0}(1-t)^{cnt(S_0,\overline{S_0})}P_{S_0}(t)dt\\ \]我们知道，
\[\int(1-x)^adx=-\frac{(1-x)^{a+1}}{a+1}+C \]那么
\[\int_0^1\sum_{S_0\subset S\\1\in S_0}(1-t)^{cnt(S_0,\overline{S_0})}=\sum_{S_0\subset S\\1\in S_0}\frac{1}{cnt(S_0,\overline{S_0})+1} \]后面这个东西怎么办？
考虑此积分：
\[\int_0^1(1-t)^kP_S(t)dt\\ =\int_0^1\sum_{S_0\subset S\\1\in S_0}(1-t)^{cnt(S_0,\overline{S_0})+k}(1-P_{S_0}(t))dt\\ =\int_0^1\sum_{S_0\subset S\\1\in S_0}(1-t)^{cnt(S_0,\overline{S_0})+k}dt-\int_0^1\sum_{S_0\subset S\\1\in S_0}(1-t)^{cnt(S_0,\overline{S_0})+k}P_{S_0}(t)dt\\ =\sum_{S_0\subset S\\1\in S_0}\frac{1}{cnt(S_0,\overline{S_0})+k+1}-\int_0^1\sum_{S_0\subset S\\1\in S_0}(1-t)^{cnt(S_0,\overline{S_0})+k}P_{S_0}(t)dt \]前面的积分也被化为 \(k=0\) 的形式。
我们希望求 \(S=V,k=0\) 的情况。
显然：
\[\forall k,\int_0^1(1-t)^kP_{\{1\}}(t)dt=0 \]好啊，现在我们可以递推。时间复杂度 \(O(3^n(n+m))\)。
估计想出来的人也不喜欢 dp。
标签：subset,cnt,int,题解,sum,overline,ZJOI2015,积分,dt From： https://www.cnblogs.com/british-union/p/possibility_good_problem.html