A Certain Game
关于题目中的样例解释翻译如下：
将队伍中的球员编号表示为 $ x_1,\ x_2,\ \ldots,\ x_k $ 的队伍称为队伍 $ \lbrace\ x_1,\ x_2,\ \ldots,\ x_k\ \rbrace $。- 在第 1 场比赛中，球员 1 所属的队伍 $ \lbrace\ 1\ \rbrace $ 和球员 2 所属的队伍 $ \lbrace\ 2\ \rbrace $ 对战，队伍 $ \lbrace\ 1\ \rbrace $ 以 $ \frac{1}{2} $ 的概率获胜，队伍 $ \lbrace\ 2\ \rbrace $ 以 $ \frac{1}{2} $ 的概率获胜。然后，这两个队伍合并为一个队伍 $ \lbrace\ 1,\ 2\ \rbrace $。- 在第 2 场比赛中，球员 4 所属的队伍 $ \lbrace\ 4\ \rbrace $ 和球员 3 所属的队伍 $ \lbrace\ 3\ \rbrace $ 对战，队伍 $ \lbrace\ 4\ \rbrace $ 以 $ \frac{1}{2} $ 的概率获胜，队伍 $ \lbrace\ 3\ \rbrace $ 以 $ \frac{1}{2} $ 的概率获胜。然后，这两个队伍合并为一个队伍 $ \lbrace\ 3,\ 4\ \rbrace $。- 在第 3 场比赛中，球员 5 所属的队伍 $ \lbrace\ 5\ \rbrace $ 和球员 3 所属的队伍 $ \lbrace\ 3,\ 4\ \rbrace $ 对战，队伍 $ \lbrace\ 5\ \rbrace $ 以 $ \frac{1}{3} $ 的概率获胜，队伍 $ \lbrace\ 3,\ 4\ \rbrace $ 以 $ \frac{2}{3} $ 的概率获胜。然后，这两个队伍合并为一个队伍 $ \lbrace\ 3,\ 4,\ 5\ \rbrace $。- 在第 4 场比赛中，球员 1 所属的队伍 $ \lbrace\ 1,\ 2\ \rbrace $ 和球员 4 所属的队伍 $ \lbrace\ 3,\ 4,\ 5\ \rbrace $ 对战，队伍 $ \lbrace\ 1,\ 2\ \rbrace $ 以 $ \frac{2}{5} $ 的概率获胜，队伍 $ \lbrace\ 3,\ 4,\ 5\ \rbrace $ 以 $ \frac{3}{5} $ 的概率获胜。然后，这两个队伍合并为一个队伍 $ \lbrace\ 1,\ 2,\ 3,\ 4,\ 5\ \rbrace $。球员 1、2、3、4、5 在整个比赛中，他们所属的队伍获胜的事件发生次数的期望值分别为 $ E_1,\ E_2,\ E_3,\ E_4,\ E_5 $，它们分别为 $ \frac{9}{10},\ \frac{9}{10},\ \frac{53}{30},\ \frac{53}{30},\ \frac{14}{15} $。
这道题看到就应该想到需要并查集。但是我们需要对于每个人，在他所在的任意时刻的集合的贡献累加到此人身上。发现这样的复杂度不好接受，比如 \(n\) 个人和 \(1\) 个人合并，那样的话复杂度为 \(O(N^2)\)，无法接受。所以需要使用启发式合并，但是这样治标不治本，因为大集合依然要更新答案。这时可以对每个集合记录一个全体累加值，当小的合并过来时，暴力的对小集合中每个元素先加上原先的集合累加量，再加入本次合并产生的，由于本次合并大集合的贡献无效，所以减去（因为大集合的集合全体累加值将会加上本次合并大集合的贡献）。
可以使用 vector（清空时不可用 clear，应该用 vector<int>().swap(balabala)） 或者单链表来进行合并（合并 \(O(1)\)）。
启发式合并的复杂度为 \(O(n\log n)\)。
分数的处理逆元可以用 exgcd/qpow。