自动搬运

查看原文

来自洛谷，原作者为

	玫葵之蝶 **

搬运于2025-08-24 21:58:14，当前版本为作者最后更新于2018-03-01 18:21:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

官方题解

首先我没有卡map，要不然好多人要挂

说一下那个东西怎么算

如果你知道一个连通块内的人的总数n

以及信仰为Ci的人的个数m的话

我们设Ni=k，那么

$ans=\frac{C(m,k)}{C(n,k)}$

然后再用个逆元就好了

（上面这个东西自己理解一下就好了，C为组合数）

然后就是怎么维护这个东西

首先我们发现只有cut没有link，然而link很容易实现

所以我们用一个经典技巧——时间倒流

我们先读入所有操作，遇到cut就标记道路被切断

然后再从后往前处理所有操作就好了

然后那个总人数可以并查集维护一下

另外信仰为Ci的人的个数可以用map启发式合并来记录

时间复杂度$O(nlog^2n)$

然后随机数据下这个东西就可以过了

其实我那个随机数据的限制可以去掉

因为Splay启发式合并的时间复杂度可以证明为$O(nlogn)$

（当然这个合并必须是把大小较小的那个以中序遍历的顺序插入另一个）

然后这个题就完了，很友好对不对？