A 待补
B
枚举当前算哪种颜色以及 ban 掉哪种颜色。
以算颜色 (1) 为例：设 ban 掉颜色 (2) 形成的连通块是 (p_1,p_2, dots,p_x)，ban 掉颜色 (3) 形成的连通块是 (q_1,q_2,dots,q_y)。
建立一张二分图，左部 (x) 个点，右部 (y) 个点。对于一个颜色为 (1) 的点，将左部包含它的连向右部包含它的。于是问题转化成了给定一张二分图，问最少选多少条边，才能使得二分图中所有点都有边覆盖它。保证没有孤立点。
显然答案就是二分图点数减去最大匹配，构造方案也比较简单。
C 待补
某 CF 题（交互题 (1)）
题意：有两个 uint32_t 范围以内的整数 (x,y)，你可以选定两个非负整数 (u,v) 并询问 (x operatorname{xor} u) 和 (y operatorname{xor} v) 的大小关系。你需要在不超过 (65) 次询问内找到 (x,y)。
首先发现 (65=2 imes 32+1)。先询问一次 (x,y) 的大小关系，如果 (x=y) 就很好做了，否则不妨设 (x<y)。
从高到低处理，对于每一位，询问 (x) 取反这一位与 (y) 的大小关系，以及 (y) 取反这一位与 (x) 的大小关系。显然有四种可能，分类讨论一下就行了。
交互题 (2)
题意：有 (n) 台机器，每台是好机器或坏机器，每次可以询问两台机器让它们互相检查，好机器一定会说真话，坏机器有可能说假话，要用不超过 (2n) 次询问问出每台机器的好坏。保证好机器个数大于坏机器个数。
考虑一个经典问题：给你 (n) 个数，定义众数为出现次数超过一半的数，只允许把所有数扫一遍，(mathcal O(1)) 内存，求众数。
维护两个变量，记录当前众数以及出现次数。如果新扫描到的数等于当前众数，次数加一；如果不等于就减一。当次数为 (0) 时，把当前众数置为新的数。
这是因为众数出现次数一定 (> dfrac{n}{2})，因此让它和其他数抵消就行了。
回到这道题：可以发现如果返回的两个结果不全是“好”，那么这两台机器里一定有一台坏机器，于是让它们抵消即可。
最后，一定剩下一些好机器，选其中一台 check 其他机器即可。
交互题 (3)
题意：有一张竞赛图，每次可以询问一条边的方向，要找到一条包含 (n) 个点的链。
考虑对 (n) 归纳，当 (n=1) 时显然是对的。
否则，假设已经找到了一条长为 ((n-1)) 的链，如果新点到链尾有边，直接加到链尾即可；如果链头到新点右边，那么插入到链头前面；否则，一定可以在中间找到形如 (x o n o (x+1)) 的路径，其中 (x) 是链上的某个点，(x+1) 是链上 (x) 的后继。具体地，每次询问 (n) 与当前二分的中点 (mid) 的边方向，如果指向 (n) 就递归到 ([l,mid])，如果指向 (mid) 就递归到 ([mid,r])。
感觉这个二分好像还有点细节。。。
交互题 (4)
题意：有一棵二叉树，其节点编号为中序遍历的 dfn。你每次可以询问两个点 (u,v)，并得知 (u) 是否是 (v) 的祖先节点。用不超过 (2n) 次询问还原整棵树。
考虑类似笛卡尔树建树的过程：按点的编号从小到大确定点的位置，每次这个点都一定在树的右链上。于是考虑维护从根节点到最右节点的链，每次询问栈顶是否是新加入的点的祖先，如果不是就弹出。每次在新弹出的点与上次被弹出的点之间连向右的边，新加入的点确定位置后向最后一个被弹出的点连向左的边。所有操作完成后在栈中元素之间依次连向右的边。
如果不理解可以画棵二叉树模拟一下。
通信题 (1)
题意：程序 A 输入一棵 (n) 个点的无标号有根树，规定每个点的儿子顺序，输出一个 (128) 位 (01) 串。程序 B 需要根据 (01) 串还原树。(nle 70)。
可以发现 (70) 个点的无标号有根树与卡塔兰数 (Cat_{69}) 一一对应，因为可以把进入某个子树看作左括号，出某个子树看作右括号。
(Cat_{69}) 正好小于 (2^{128})，于是用 dp 求出字典序第 (k) 大的合法括号序列是什么，以及某个括号序列是第几大的就行了。
通信题 (2)
题意：程序 A 输入一个 (10^{18}) 范围内的非负整数，输出一棵点数不超过 (100) 的无标号无根树，程序 B 输入这棵树，输出原数。
考虑怎么样让这棵树表示一个数：我们组成一条长为 (20) 的链，并用一些点标志这条链的头尾。再在链上的每个点上挂 (0sim 3) 个点，这样至多 (4) 个点就可以组成 (3) 个 bit。于是这样能表示的数就是 (0sim 8^{20}-1)，大于 (10^{18})。
通信题 (3)
题意：程序 A 输入一张 (n) 个点的有标号的无向简单图，输出一张 ((n+12)) 个点的无标号无向简单图。程序 B 输入无标号图，还原有标号图。(nle 1000)。
多出来 (12) 个点是干啥的？我们把其中的 (10) 个点向原图中的点连边，第 (i) 个点向所有标号二进制第 (i) 位为 (1) 的点连边。剩下的两个点中，一个点向原图中的所有点以及那 (10) 个点连边，剩下那个没被连边的点用来向那 (10) 个点连边，以标识那 (10) 个点。
可以发现 (n) 略小于 (1024)，所以表示最高位的点的度数一定小于表示最低位的点的度数。于是就可以区分出高低位了。
通信题 (4) 待补
题意：程序 A 和 B 各会输入一个 ({1,2,dots,n}) 的子集。程序 A 可以向交互库输出一个 (1dots n) 的排列，然后向程序 B 提供两个 bit 的信息。程序 B 也可以向交互库输出一个 (1dots n) 的排列，此时交互库会向程序 B 返回两个排列复合起来是不是只有一个轮换（只能询问一次）。最后程序 B 需要判断：二者的集合有没有公共元素。
通信题 (5)（IOI2020 网络站点）
题意：程序 A 输入一棵树，并将这棵树重标号。程序 B 需要处理多次询问，每次以新的编号给定树上的两个点 (s,t) 以及与 (s) 相邻的点的编号，B 需要回答从 (s) 走到 (t) 的路径上包含与 (s) 相邻的哪个点。重标号必须是 (mathbf{1sim n}) 不重不漏。
部分分：重标号只需要在 (1sim n^2) 内不重复即可。
先考虑部分分：可以用每个点的标号记录它的欧拉序 ((st_u,ed_u))。这样我们就可以根据 (t) 的编号知道它在 (s) 的哪个子树内，或者需要从 (s) 往上走。
正解：dfs 的过程中，对于深度为奇数的点，入栈时给它赋一个 dfn；否则出栈是给它赋一个 dfn。这样画画图就可以发现能确定 (t) 在 (s) 的哪个子树内了。