「PKUWC 2018」随机游走（容斥原理 + 高斯消元）

题目大意

「PKUWC 2018」随机游走（LOJ 2542）

给定一棵 $n$ 个结点的树，根为 $r$。有 $Q$ 个询问，每次给定一个点集，问从根开始随机游走，到达这个点集中的所有点的期望步数。

数据范围：$n \le 18, Q \le 5 \times 10^3$。

思路分析

这个 $Q \le 5 \times 10^3$ 好像没什么用啊 QwQ

考虑预处理出每个点集的答案，然后对于每个询问直接查表。

这里介绍一下 Min-Max 容斥：

$$\begin {align*} & \max\{x_1, x_2, \cdots, x_n\} \\ = & \sum_{i} x_i - \sum_{i < j} \min \{x_i, x_j\} + \sum_{i < j < k}\min \{x_i, x_j, x_k\} - \cdots \\ = & \sum_{S \subseteq \{x_1, x_2, \cdots, x_n\}} (-1)^{\vert S \vert - 1} \cdot \min \{S_i\} \\ \end {align*}$$

这么算 $n$ 个数的最大值有什么好处呢？考虑 $x_i$ 是随机变量，并且某个子集的最小值的期望比较好计算的情况。由于期望的线性性，我们可以使用 Min-Max 容斥，分别计算每个子集最小值的期望即可得到它们最大值的期望。注意到对于任意的两个随机变量 $x, y$，都有 $E(x + y) = E(x) + E(y)$，不要求 $x, y$ 独立。

对于这个问题，我们设共有 $m$ 个点，到达第 $i$ 个点的时间为 $t_i$，我们要求的就是 $E(\max {t_i})$。考虑计算 $E(\min {S_i}) (S \subseteq { t_i })$，也就是第一次到达一个点集的期望时间。

对于一个子集中的点，如果它到根的路径上已经存在点了，那么它就没有用了。我们扔掉没用的点以后，树的所有叶子结点一定都在点集中了。我们列出随机游走的方程，使用高斯消元法求解即可。最后，将每个点集的答案乘上容斥系数，再使用一遍高维前缀和，就可以求出原问题的答案了。

共要枚举 $2^n$ 个点集，暴力高斯消元的复杂度是 $O(n^3)$ 的，总复杂度 $O(2^n n^3)$，似乎不可通过。考虑图的结构是一棵树，我们可以 “手动高斯消元”。设 $L$ 是叶子结点集合，第 $u$ 个结点的度数是 $d(u)$，答案是 $f(u)$，那么有：

$$\begin {cases} f(u) = 0 & (u \in L) \\ f(u) = 1 + \displaystyle \frac{\sum_{(u, v) \in E} f(v)}{d(u)} & (\text{otherwise}) \end {cases}$$

发现 $f(u)$ 肯定能表示成 $a(u) \times f(\text{fa}(u)) + b(u)$ 的形式。这样，我们从下往上递推，就可以直接算出 $a(u), b(u)$。算到根结点时，因为它没有父亲，所以 $b(u)$ 就是答案。这样，时间复杂度降低到了 $O(2^n n)$，可以通过本题。

代码实现

#include <bits/stdc++.h>