> 考虑期望的可加性，答案就是 $\sum_{f_i}$
有个小学弟产生了一个疑问， 难道我们求出来的不是每个点都被执行一次操作的期望次数吗？
先回答为什么不是：
加入存在一条边 $1 \rightarrow 2$ , 我们删掉 $1$ 势必会把 $2$ 也带走，也就是变量 $X_b$ 与 $X_a$ 有关，所以不能直接相加。
再来回答为什么是正确答案：
$f_i$ 表示的是有 $f_i$ 的概率 $i$ 会被染色，而不是我们要去染 $i$, 有$f_i$ 的概率会成功。换言之，$E(\sum X)$ 代表的是整个点集有期望有多少点会被染色，而不是将整个点集染色期望多少次。
那每个点都被染色的概率是多少呢？
考虑染色序列必然是由下到上的，（对于树而言）。
那么对于每个点，都要在这个染色序列的第一个……
哈哈:innocent:，答案就是 $\prod f_i$
by guodong @ 2021-09-15 20:06:31
改成二楼那个可能比较好理解 ( 其实就多加了一个引用）
by guodong @ 2021-09-15 20:07:09