Minimax
显然每个叶节点的值都是能取到的。
设 $dp_{i,j}$ 表示点 $i$ 取到第 $j$ 小的值的概率。当 $i$ 是叶节点或者仅有一个儿子是转移很容易，有两个儿子时的转移也不难写出
$$
\begin{aligned}
dp_{i,j}&=dp_{ls,j}\times\left(\sum_{k<j}dp_{rs,k}\times p_i+\sum_{k>j}dp_{rs,k}\times(1-p_i)\right)\\&+dp_{rs,j}\times\left(\sum_{k<j}dp_{ls,k}\times p_i+\sum_{k>j}dp_{ls,k}\times(1-p_i)\right)
\end{aligned}
$$
考虑开 $n$ 棵线段树来维护每个点对应的 $dp$ 数组，那么转移时直接线段树合并即可。
具体的，每次合并时记录两边的贡献，并在线段树上打乘法标记即可。这一部分可以结合代码理解一下。
时间复杂度 $\mathcal{O}(n\log n)$，空间复杂度 $\mathcal{O}(n\log n)$。
Slay the Spire
首先考虑，假如已经随机出了 $m$ 张卡，怎样才能使总伤害最大。
容易发现的是，因为强化牌上的数字都大于 $1$，所以多选强化牌必然更优；而我们选的必然是最大的那些牌。
那么就可以得到一个贪心策略了：
- 如果强化牌的数量 $<k$，则选所有强化牌，然后选最大的攻击牌补至 $k$ 张。
- 否则，选最大的 $k-1$ 张强化牌，然后选最大的一张攻击牌。
那么我们考虑计算所有最优选择方案在多少种抽取方案中。
首先将强化牌和攻击牌各从大到小排序。
设 $f_{i,j}$ 表示前 $i$ 张强化牌选了 $j$ 张所有方案的强化数值之和，$g_{i,j}$ 表示前 $i$ 张攻击牌选了 $j$ 张所有方案的攻击数值之和。
容易得到转移
$$
\begin{aligned}
f_{i,j}&=f_{i-1,j-1}\times w_j+f_{i-1,j}\\
g_{i,j}&=g_{i-1,j-1}+{i-1\choose j-1}\times w_j+g_{i-1,j}
\end{aligned}
$$
然后枚举随机出的强化牌的数量，利用组合数计算出答案即可。时间复杂度 $\mathcal{O}(Tn^2)$。
斗地主
非常抱歉，这个题鸽了。
随机算法
设 $dp_S$ 表示子图 $S$ 的正确率，$mx_S$ 表示子图 $S$ 的最大独立集大小。
考虑转移。记 $T_i$ 为 $S$ 去掉 $i$ 和所有与 $i$ 相连的点后形成的集合。那么首先有
$$
mx_S=\max_{i\in S}\left\{mx_{T_i}\right\}+1
$$
然后有
$$
dp_S=\frac{\sum_{i\in S}[mx_S=mx_{T_i}+1]dp_{T_i}}{|S|}
$$
时间复杂度 $\mathcal{O}(n2^n)$。
猎人杀
考虑一个比较神仙的转化：每个人死后不让他退场，而是给他一个标记；选择对象时如果选中了一个有标记的人就重选一次。可以发现这样子答案是一样的。
这个转化有一个好处：分母 $\sum_{j=1}^mw_{i_j}$ 恒等于 $\sum_{i=1}^nw_i$，也就是说分母不会变了。
接着可以考虑一个容斥。我们钦定 $S\;(1\notin S)$ 中的人在 $1$ 之后死，那么容斥系数为 $(-1)^{|S|}$，概率为
$$
\frac{w_1}{\sum_{i=1}^nw_i}\times\sum_{i=0}^\infty(1-\frac{w_1+\sum_{j\in S}w_j}{\sum_{j=1}^n w_j})^i
$$
后面的东西可以等比数列求和，整个式子化简为
$$
\frac{w_1}{w_1+\sum_{i\in S}w_i}
$$
可以发现不同的 $\sum_{i\in S}w_i$ 只有至多 $100000$ 个，因此我们可以考虑对于每个 $\sum_{i\in S}w_i$ 计算出它前面的系数。
容易发现这是一个背包的过程：对于每个 $w_i$，加入它后系数乘上 $-1$。但是直接背包的话复杂度无法承受。
考虑生成函数。第 $i$ 个人的生成函数是 $-x^{w_i}+1$，我们只需要将第 $2$ 到 $n$ 个人的生成函数乘起来即可。可以使用分治 FFT 完成。时间复杂度 $\mathcal{O}(n\log^2 n)$。
随机游走
考虑 min-max 容斥的式子
$$
E(\max\{S\})=\sum_{T\subseteq S}(-1)^{|T|+1}E(\min\{T\})
$$
如果我们把第一次被访问到时走的步数作为每个元素的权值，那么这里的 $\max\{S\}$ 即为访问完 $S$ 中所有元素的步数，$\min\{S\}$ 即为第一次访问到 $S$ 中某一个元素的步数。
那么我们仅需要求出从 $u$ 出发第一次访问到 $S$ 中某个元素的期望步数即可。
设 $f_{u,S}$ 表示从 $u$ 点出发，访问到 $S$ 中某个元素的期望步数。容易列出方程
$$
f_{u,S}=\frac{\sum_{(u,v)\in E}f_{v,S}}{deg_u}
$$
直接高斯消元显然会 T。因为这是在树上，所以可以使用一种叫做「树上高斯消元」的科技。
设 $f_{u,S}=a_u\times f_{fa,S}+b_u$，然后推一推式子：
$$
\begin{aligned}
f_{u,S}&=\frac{f_{fa,S}+\sum_{v\in son_u}f_{v,S}}{deg_u}+1\\
&=\frac{f_{fa,S}+\sum_{v\in son_u}(a_v\times f_{u,S}+b_v)}{deg_u}+1\\
&=\frac{f_{fa,S}+\left(\sum_{v\in son_u}a_v\right)\times f_{u,S}+\left(\sum_{v\in son_u}b_v\right)}{deg_u}+1
\end{aligned}
$$
设
$$
\begin{aligned}
suma_u&=\sum_{v\in son_u}a_v\\
sumb_u&=\sum_{v\in son_u}b_v
\end{aligned}
$$
则
$$
f_{u,S}=\frac{f_{fa,S}+suma_u\times f_{u,S}+sumb_u}{deg_u}+1
$$
化简得到
$$
f_{u,S}=\frac{f_{fa,S}}{deg_u-suma_u}+\frac{sumb_u+deg_u}{deg_u-suma_u}
$$
比较系数得到
$$
\begin{aligned}
a_u&=\frac{1}{deg_u-suma_u}\\
b_u&=\frac{sumb_u+deg_u}{deg_u-suma_u}
\end{aligned}
$$
发现这个仅和子树中节点有关，那么就可以直接在树上 DFS 求出了。注意边界问题：当 $u\in S$ 时 $f_{u,S}=0$，所以此时 $a_u=b_u=0$。另外根节点 $x$ 没有父节点，因此 $f_{x,S}=b_x$。
现在我们已经求出了所有的 $f_{u,S}$，而实际上 $E(\min\{S\})$ 就是 $f_{x,S}$，那么我们就可以通过 min-max 容斥求出答案了。时间复杂度 $\mathcal{O}(Q2^n)$。
仔细观察 min-max 容斥的式子，可以发现是子集和的形式，于是用 FWT 预处理出所有子集和即可。时间复杂度 $\mathcal{O}(n2^n)$。