题解 P4255 【公主の#18文明游戏】

· · 题解

官方题解

首先我没有卡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)

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

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