趣味并查集

· · 个人记录

问题。Alice 和 Bob 在玩一个卡牌游戏。每张卡牌的正面和背面分别写了一个数字。对于一个卡牌的集合 S,首先从 S 中随机抽取一张卡牌。假设正面写了数 x,背面写了数 y。Alice 只能看到卡牌的正面,Bob 只能看到卡牌的背面。Alice 和 Bob 会轮流尝试猜测对方看到的数字,直到有一方猜测成功为止。他们只会在完全确定对方数字是什么的时候才会猜测。以下是一个游戏进程的例子:

  1. Alice:我不知道 Bob 看到了什么数字;
  2. Bob:我不知道 Alice 看到了什么数字;
  3. Alice:我不知道 Bob 看到了什么数字;
  4. Bob:我知道 Alice 看到的数字一定是 x

Alice 和 Bob 都是绝顶聪明的,且他们都知道集合 S。令 F(S) 为有多少种选取卡牌的方式使得 Alice 能够先于 Bob 猜到对方看到的数字。同样,令 g(S) 为有多少种选取卡牌的方式使得 Bob 能够先于 Alice 猜到对方看到的数字。注意可能 |f(S)|+|g(S)|\ne|S|,因为对于有些卡牌,Alice 和 Bob 永远无法知道对方看到的数字是什么。

初始 S 为空,你需要处理 q 次操作,每次操作会往 S 内添加一张正面写 x,背面写 y 的卡牌,你需要求出当前的 |f(S)|,|g(S)|

--- 不理解题意的参考 [一个小的推理题(猜牌:一个告诉点数,一个告诉花色)_a知道点数 b知道花色-CSDN博客](https://blog.csdn.net/weixin_37477009/article/details/111655411) 或者 [趣题:无限多层嵌套的逻辑推理 ](http://www.matrix67.com/blog/archives/6377)。 考虑经典套路,开 $2V$ 个点 $1,\dots,V,1'\dots,V'$,将 $(x,y)$ 视为 $(x,y')$ 的边,形成一个二分图,记 $x$ 为左部点,$x'$ 为右部点。 则注意到这是一个反复迭代的过程: 1. Alice 删掉左部点中的叶子 $T$($\deg=1$),然后 $f(S)\gets f(S)\cup T
  1. Bob 删掉右部点中的叶子 T\deg=1),然后 g(S)\gets g(S)\cup T

分连通块考虑,如果某个连通块是树,则只有直径中点不会被删;否则,只有不在环上的点会被删除。