好像也有个叫法叫最值反演？
就是这样的一个柿子：
用 $ Max $ 来求 $ Min $ 也一样可行。
证明不太难，所以干脆咕了，随便找个证明。
由于期望的线性性，以上公式对于每个元素的期望也是成立的，
可以写作 $ E( max(S) ) = \sum\limits_{T \subseteq S} E( min(T) ) $ 。
这个是比较有用的，因为很明显 $ E( max(S) ) \ne max( E(S) ) $ ，这个是不容易轻易用正常方法求出的。
要求求出 $ E( max(U) ) $ 。
很明显求不出来所以考虑改求 $ E( min(S) ) $ 。
考虑有 $ P( min(T) == k ) = P( S \oplus U ) ^ {k-1} ( 1 - P( S \oplus U ) ) $ 。
几何分布，很容易得出 $ E( min(S) ) = \frac{ 1 }{ 1 - P‘( S \oplus U )} $ ，其中 $ P‘(S) = \sum\limits_{T \subseteq S} P(T) $ 。
$ FWT $ 变换一下即可出解，注意特判 $ \le eps $ 。
依然改求 $ E( min(S) ) $ 。
也就是求经过某个集合中至少一个点时的期望步数。
设 $ f_{S,x} $ 为从 $ x $ 出发，到达 $ S $ 中某个点时的期望步数，很明显 $ E( min(S) ) = f_{S,root} $ 。
为了分离父亲对其贡献，考虑转化成 $ f_{S,x} = A_{x} * f_{ S , fa_{ x } } +B_{x} $ 。
解完之后发现与父亲的值无关，可以直接树形dp。
然后直接minmax容斥就完事了。
$ \max\limits_{k}(S) $ 表示第 $ k $ 大。
证明需要用到二项式定理，也咕了。
依然对期望成立。
注意到 $ |n-k| \le 10 $ 。
很明显答案要求 $ E(\min\limits_{k}(U)) $ ，等效于 $ E(\max\limits_{n-k+1}(U)) $ 。
那么求 $ E(min(S)) $ 就好。
问题来了。
$ n \le 1000 $ ，不能直接做。
但是 $ m \le 10000 $ ，可以从这里下手设计dp。
然后再往下的我不会了。
很明显 $ E(min(S)) = \frac{1}{ \sum\limits_{i \in S} p_{i} } $ 。
考虑用dp统计对于每个 $ \sum\limits_{i \in S} p_{i} $ 的值的系数和。
具体的dp设计它咕了。
原文：https://www.cnblogs.com/rikurika/p/13320899.html