task21

[TOC]

1. QOJ11623 - Construct Point [E]

题面

组数据，每次给定一个二维平面上的非退化三角形，保证顶点为整点，请找到任意一个严格在三角形内部的整点，或报告不存在

，坐标范围在 内

题解

Flamire 做法

Sol

判断是容易的，使用皮克定理计算面积比较即可，但是这对解决这个题并没有什么用。

将三个点按照横坐标排序，拆成两部分，对于一边的情况，相当于我们有两个分数满足 ，我们要找到一个分数 满足 且 最小

这个可以在 Stern-Brocot Tree 上实现，细节略为繁琐，复杂度

题解做法

Sol

取整数 ，对所有点进行 的变换。可以发现进行这个变换之后，每个整点对应的还是整点，且每个非整点对应的还是非整点，并且由于我们只是将平面拉伸了一下，因此点和线的相对位置关系应该不改变。

那么我们就可以通过拉伸操作，把原三角形 拉成一个容易处理的形式。

首先，我们将 通过平移放到 。

然后，我们将 移动到坐标轴上，由于我们可以不断进行 和 ，所以我们可以通过类似辗转相除的方式将 放到坐标轴上

再使用一些翻转方式将 翻到 轴正半轴上，此时 ，那么我们可以不断执行 的操作，调整 的大小，我们再通过一系列这样的操作和翻转操作，令

此时这个三角形若不包含 ，则一定不包含任意整点，因此只要判断 ，再把所有操作求逆即可，复杂度

---

2. QOJ11622 - Colorful Doors [E]

题面

有一段长为 的桥，用 个门隔开，第 个门分割第 段桥和第 段桥。门有颜色，且 种颜色每种恰好有两个

当你在第 段桥时，你会进入第 个门，然后被传送到另一个颜色和第 个门相同的门右边那段桥

你会从第 段桥开始，一直这样走直到走到第 段桥为止。

现在给定一个长为 的 01 串 ，表示 中的每段桥有没有被你经过过，你需要构造一个匹配门的方式使得其成立

题解

Sol

认为 。把每个门按照其相邻的两段桥的 01 称呼。

那么不难发现，11 门只能内部连，00 门只能内部连，10 门必须连 01 门，因此奇偶性不对可以直接判掉。

00 门内部连显然怎么连都无所谓，随便连即可。

我们需要让 11 门和 10 门的连接方式使得所有 1 的位置都连通。

可以发现，当 11 门的数量是 的倍数时，我们可以直接将所有 10 门和下一个 01 门匹配，这样会等价于一个 全 1 的问题，而如果此时 11 门的数量是 的倍数，我们可以 1 2 1 2 地匹配，将相邻的四个门消掉，因此可以构造

否则，11 门的数量是模 余 的，可以发现此时全 1 是构造不出来的。证明可以考虑增量，每加一对门一定会导致连通块个数奇偶性变化。

因此，我们一定要在连 10 门的时候，把某些 11 门独立出来形成一个环，而可以发现只要我们将 11 门拆成了一个链和一个环之后，可以分类讨论环长模 的余数，总是可以构造出来解

实现即可。

---

3. QOJ10871 - Joy of Sushi [E]

题面

给定一个长为 的数列 和一个长为 的数列 ，依次进行如下三次操作，称为一轮：

• 对于 ，令
• 将 分别循环右移一位

求最少多少轮操作之后所有 同时为 的倍数

题解

Sol

想办法固定 不动，可以发现这个操作的周期是 。

对于 ，它前 次操作都是 ，接下来 次操作是 ，一直这样下去，最后 次操作 ，一共 次操作

而对于 ，可以发现，它的操作序列就是上述操作序列循环左移 次的结果

因此，我们可以定义一个序列 ，下标为 ，那么 的操作就是从第 次操作开始的循环位移

可以发现，一个整周期的效果相当于给所有 加上一个定值 ，因此我们只要判断前面的每一个时刻是否满足所有 均相等，然后判断即可

定义 的前缀和为 ，我们需要对每个 判断是否有，对于 ， 全部相等

转化为相邻项 和 的这个值差等于 ，可以发现我们就是要求 的值等于某个值，也就是说这个问题实际上是我们有一个序列 ，我们要对每个 判断是否有

对于模 相同的 ，这个就是循环位移，可以用多项式哈希维护，因此总复杂度为

---

4. QOJ10862 - Advanced Evolution Studies [E]

题面

给定正整数 以及 个限制 ，保证 ，你需要构造一棵有根树 满足如下条件，或者判断无解：

• 其点数在 内
• 对于每个限制 ，都有 是 的严格子孙

题解

Sol

注意到我们可以使 中 的点都是叶子：如果一个点 不是叶子，那么我们将这个节点更改为一个新的编号，然后把 挂在这个节点下面不会改变任何点对的 LCA

把这棵树看成从一堆单点合并成全集的过程。正着操作的影响不好描述，因此我们考虑倒过来。

每个限制相当于合并出 前我们要么有 ，要么有

倒过来就相当于我们需要将全集拆成若干个小集合，而拆一个集合 的时候有如下限制：

• 若对于某个限制 ，满足 ，则 必须划分到同一个小集合内，且如果 在同一个小集合内，那么 必须都在同一个小集合内

而注意到把集合拆的更碎一定不会更劣，因此我们进行如下过程：

• 初始将 中每一个元素划分为一个小集合
• 将所有 的小集合合并
• 如果当前有某个限制的 在同一个小集合内，那么将 的小集合合并

最后如果得到的是全集，那么一定无法合法分割，返回无解，否则递归进行

第三步可以使用启发式合并，每次合并探测更小的那边的所有连边，复杂度

---

5. QOJ10697 - Judge Error [E]

题面

给定一个 个点的无向图 ，判断 是否有唯一的完美匹配，有则输出方案

，边数

题解

Sol

画一画可以发现看起来一个点双如果有完美匹配，则一定不唯一

可以发现这可以推出边双的完美匹配不唯一：我们建出圆方树，可以根据子树点数奇偶性判断每个割点要跟哪边匹配，我们把这个看成一个方向，那么一定存在一个所有相邻的方向都向内的点双，这个点双必须是一条边，这意味着图想要有解必须存在割边

这也为我们提供了一个对有解的图构造解的方式：我们每次找到任意一条割边，根据两边连通块的大小奇偶性判断是这条边是直接匹配还是删除，如此递归即可构造

朴素实现即为 ，使用一些手段将找割边优化到 可以做到总复杂度

---

6. QOJ10693 - Flappy Bird []

题面

二维平面上有一个高为 的通道， 和 为不可逾越的障碍

有 个额外障碍，这些额外障碍可以描述为：给定 ，表示 和 的两条线段为障碍

求 到 的最短路（可以在二维平面上以任意方向移动）

题解

Sol

同 ARC001D，摘录一下题解。

称 的线段为下障碍， 的线段为上障碍，可以发现我们的最短路一定是一条折线，每个折点都是障碍端点，并且我们只能在下障碍端点右转，上障碍端点左转

从起点出发，走出一个上边界 和一个下边界 ，满足 只能左转（且只经过上障碍端点）， 只能右转（且只经过下障碍端点）

分别是凸包，新加入一个障碍时，我们只要加入新的障碍端点，更新凸包即可

如果加入某个障碍后 和 相交，那么一定有 或 中的某一个只有一条直线，不妨设为 ，此时可以发现我们最优解一定会走 中第一条线段，将起点移动至这条线段的终点，继续执行上述过程

可以使用双端队列 维护。

---

7. QOJ10688 - AmazingTalker [E]

题面

给定 个二元组 ，请给这 个二元组之间连边，使得对于任意一个二元组 ，其邻居 有多于一半满足 ，或者报告无解

要求构造方案边数不超过 。

题解

Sol

意义不明。

画到二维平面上，如果两个点为左上-右下的关系的话，在不考虑边数限制的情况下连上它们一定是不劣的，称这样的边为实边，其余边为虚边

进一步发现，不会有一条长为 的递进的虚边链（即 的链，其中两步都在向右上走），因为我们可以替换为连接首尾的一个虚边

因此，连完所有实边之后，设一个点的度数为 ，那么此时不合法的即为 的点，这些点必须向左下角连至少一条虚边，而连一条虚边就足够了

只需要判断每次 是否能在左下角选出合法点即可，容易做到

接下来解决边数限制的问题，一个点如果被某个 选到了就给它的 加 ，那么最后每个 的点只要连 条实边即可

随便使用二维偏序数据结构连足够多的边即可，，因此所有点的实边度数之和不超过 ，而虚边最多 条，因此总共边数不超过

---

8. QOJ10543 - Square Stamping [E]

题面

给定 个纵坐标为 之一的点，求最少用多少个 的正方形（包含内部与边界），使得它们的并集覆盖所有点

题解

Sol

将三条线从上到下编号为 ，考虑最左边的点，如果最左边的点在 或 上，那么我们一定选 矩形，当在 上时我们可以选择取 还是 上的矩形

而不妨设取了一个 矩形，我们需要检查覆盖的这段横坐标的 上是否有点，有点的话我们再用一个矩形覆盖，然后再检查 的范围，一直这样重复下去

注意到每次 交替停下的时候，我们的状态都是某个横坐标之前的点都被覆盖完了，因此设状态 表示只考虑横坐标 以后的点，都覆盖需要用的最小矩形数

那么如果暴力转移，我们就得到了一个状态数 ，转移 ，总时间复杂度 的做法

考虑优化，注意到我们过程中所有的状态形如 被覆盖到了 ，然后 被覆盖到了 的一个位置（或者 和 ），不难发现 越大答案越小，且 的答案最多比 大

因此，我们再额外存 表示此时 覆盖到了横坐标 ， 至少要覆盖到多少才能使答案小于 ，如果 时答案仍为 ，我们就认为 ，同理存一个

转移 和 可以二分，经过一些处理可以使复杂度为

本题还有一个记忆化搜索做法，即直接按照这个贪心执行，记忆化所有状态。出题人在题解里声称这是 的，但是略去了证明，感觉多少有点毛病，令人火大。

目前我还没有找到任何有道理的证明，个人倾向于这个实际上是没有道理的，只不过不好卡。

---

9. QOJ10083 - Single-Crossing [E] ⭐

题面

给定 个 的排列 ，你需要重排这 个排列之间的顺序，得到 的方案，使得对于每对 ，按照 的顺序排列后， 和 的相对顺序只会变化一次

给出构造或判断无解

组数据。

题解

Sol

如果我们确定了 ，那么整个问题即可确定：我们将 变为 ，其余排列类似变换之后，一定按照字典序排列，并且每轮交换的两个数一定满足前面的更小，只需要顺次检查每对 是否合法

这个也是可以检查的，我们将条件重新表述为：对于每个值 ， 到 的过程中新运动到 前面的所有元素必须

这个可以扫描线+树状数组维护最值解决，因此我们固定 判断合法是可以做到 的

接下来，我们就是要求出 ，可以证明，合法的 只有两个，即一个合法顺序和它的 reverse

有若干种方式求出 ：

• 考察一对 ，如果 和 的相对关系都出现了，那么我们可以将其分为两个集合 ，第一次时可以任意将一个集合放在前面，而递归下去之后必须要判断在外面大小关系，决定要把哪个放在前面

  找到一对相对关系改变的 可以任意选两个排列 ，找到它们第一个不同的位置

  但我们找到 的层数可能很大，复杂度退化为

  我们选取 时采用随机，在最终的 中 和 有 的概率都在此时集合的前 ，这样能保证期望 次之后就能将问题规模除以 ，不符合概率判断无解即可

• 也是优化上面的过程，观察我们不一定要找到 ，只要我们找到任意一个 ，并且我们划分开哪些排列是 ，哪些是 ，分别运行上面的 check 算法即可。因此，我们在上述的分裂算法中，每次走小的一边即可

• 对两个排列 ，定义为 的逆序对个数，也可以视作将 和 排成一排，将相等元素之间连线的交点数

  可以发现如下结论：，证明可以考虑上述画线的理解，右式即为计数所有折线之间的交点数，而由于任意两个元素代表的折线只会相交一次，所以这就直接等于所有元素的交叉次数

  因此，我们任意固定一个排列 ，找到与其 值最大的排列，其一定为 或

总复杂度

---

10. CTT2023 - 士兵游戏 [E]

题面

构建一棵 个点的树，对于每个 ， 向 有连边，其中 表示 的最小质因子

求 个点两两路径长度之和

题解

Sol

考虑每条边被贡献了多少次，转化为统计子树大小。

对于一个数 ，它子树中的数一定都形如 ，且 的最大质因子要小于等于 的最小质因子，我们就是要计数满足 的 数量

枚举 ， 时这个值即为 ，因此我们可以一开始将所有点按照 算

当 时，设 ，那么 ，也就是说， 的所有 对我们后面的事情都是等价的，因此我们把这样的 放在一起算，进行整除分块

因此我们的流程就是：枚举一个 的块，然后求这个块内 的 数量，并且求 的 的 数量

因此，我们需要处理出 和 ，分别表示 的数中 和 的个数， 只用存块筛处的值， 只用存 的质数

的转移就是正常的 min25 筛，只用更新 的位置，暴力写即为 。

但 的转移无法跳过 的位置。

注意到 的转移为 ，因此我们可以枚举 ，然后使用树状数组快速更新 ，这样我们只需要枚举所有 的块筛，因此复杂度为

枚举 块的部分也是枚举所有 的块筛，可以类似分析

那么此时我们就得到了一个 的算法，已经可以通过。

进一步地，可以发现我们在枚举到 时，只需要算出 位置的 和 值，所以我们枚举 的块筛的时候只需要枚举 的即可

复杂度：

• 当 时不超过
• 当 时不超过

积分一下可以得到枚举量级为 ，再使用树状数组可以把这部分做到

因此总复杂度为 ，理论上求 的部分也可以优化到 ，但是毛估估一下已经跑得很快了。

---

11. CTT2023 - 解谜游戏 [E] ⭐

题面

交互题，有一个隐藏的 的排列 ，每次你可以询问一个 的排列 ，交互库会返回有多少位置满足

你需要在 次操作内确定 ，

题解

Flamire 做法

Sol

没有什么出发点，考虑随机直到找到错排为止。根据某些结论，期望随机 次之后就能找到一个错排

但手玩一下可以发现有一个错排之后还是有些困难。直观感受可以画到一个矩形上， 表示 是否为真

那么一个错排相当于我们排除掉了一条斜线，但在此基础上构造别的结构依然比较困难。

因此我们可以考虑随机直到 和 循环左移一位都是错排，这样随机依然是常数次。

这时，我们交换 的相邻两位，这两位会分别错位 和 ，而错位 的情况我们是知道的。

也就是说，此时我们可以选出一个 的独立集，然后询问这里面有多少个位置是对的

那么二分即可，一个环可以拆成三个独立集，询问次数是 ，会被卡常，加一个推断，如果一行一列有 个 0 就填出 1，填出 1 就 ban 掉该行该列的所有其它位置，这样就可以通过了

提交记录做法

Sol

考虑随机出一个错排。在错排上交换两个位置 ，询问相当于得到 ，也就是说询问相当于得到置换环上这条边是否存在

而可以发现，我们也可以找出一些互不影响的交换，然后得到它们的询问的和

换个方式重新表述一下我们的问题：现在有一张完全图，每次询问我们可以询问一个匹配中有多少条边，还原一个置换环图

那么解决方式就比较显然了，一个完全图可以拆成 或 组匹配，我们在每组匹配上分别二分出所有边即可

询问次数 ，常数很小，可以直接通过。

---

12. QOJ10045 - Permutation Recovery [K] ⭐

题面

给定一个 的矩阵 ，按照如下方式生成：选取 个 的排列 ，将这些排列排到 的前 行，将 排到 的后 行，然后再对 每列中的元素打乱

现在给定一个 ，你需要还原任何可能的

题解

Sol

将点 向第 列中的每个数连边，不难发现由于我们加入了每个排列及其逆排列，最终这张图会形成若干条重边双向边，缩完之后我们得到的应该是一个度数为 的正则无向图，而我们要做的就是将这个图拆为若干个排列图

如果这张图是二分图，我们就知道一定可以拆成 个排列，问题就马上解决了，但这不是二分图

如果 是偶数，那么我们可以求一个欧拉回路，然后将这张图拆成两张 -正则图，递归下去做，但是 不一定是偶数

那么我们可以尝试去给每个点匹配前驱和后继，我们把每个点拆成入点 和出点 ，将一条边 拆成 ，这样我们建出来了一个 -正则二分图

但是这样有一个问题：对于一条边 ，我们有可能把 和 相互匹配，但是这样的话 之间应该有两条边，这不合法

如果我们能对这个图定向的话，也许就能匹配了。

因此我们求出欧拉回路，将所有边按照欧拉回路定向。按照上述方式建出来的图是一个 -正则图，因为每个点都有 条入边和 条出边

因此这时我们跑一个二分图边染色，就能解决所有问题了。

复杂度 或者 ，取决于求最大匹配的方式，我不知道直接跑 的二分图边染色复杂度是否正确，但好像跑的挺快。

---

13. QOJ10037 - Build Well [E]

题面

给定 ，以及一个长为 的数组 ，你现在有长为 的弧，每种 都有无穷多个

求是否存在两种把这些圆弧拼成一个完整的长为 的环的方式，使得每个断点的坐标都是整数，且这两种方式之间断点不重叠

题解

Sol

如果我们选择了一些元素和为 ，且这些元素中不存在 ，那么我们把这个拼法循环 ，就可以得到一个合法的解

否则，长为 的弧一定被塞到了别的弧的内部，我们不妨假设两种方式的长度集合相同，设选的元素集合为 ，其中有 个 ，那么每个 的元素 最多可以塞 个

也就是说，，化一下式子可得

而求最小凑出的个数仍然不太好算，我们再观察一下：

• 如果存在某个长度 ，使得 ，那么我们只用 和 即可，进一步发现除了 和当 为奇数时 ，其余 均满足条件
• 而如果不满足上述条件，可以发现我们也可以先选一个 ，再选尽可能多的 ，最后最多剩一个
• 如果 是偶数，我们也可以全选
• 否则，显然我们不存在一种方式满足

而这时每种凑出 的方式都至少有 个端点，显然无法使断点不重合

---

14. QOJ10007 - Holes in Queue / CF1060G - Balls and Pockets [E/K] ✔️

题面

有一个无限长的序列 ，初始为 ，给定一个集合 ，一次操作会同时删除所有 的

次询问，每次询问给定 ，询问操作 次之后 的值

Holes in Queue：所有 均相等

Balls and Pockets：无特殊限制

题解

Flamire 做法（仅限 Holes in Queue）

Sol

这个操作看起来非常难维护。

因此我们换一个方向考虑，会被 删掉的数一定是 ，因此我们直接将这些数从原序列中删除，接下来 删掉的数一定是此时的第 个数

那么我们就得到了一个求一个数最后排名的算法，倒过来可以变成从排名求数的算法

我们现在的过程为：顺序扫 ，每次在第 个数前插入一个空数，有若干询问点，我们需要求出每个询问点在做完所有操作之后到了哪里

考虑观察一下这个询问，可以认为我们每次操作分成了 个长为 的块，但是加入一个空数之后就变成了长为 的块，并且下一次操作我们依然是要分成 个长为 的块，因此这之间看起来有某种联系，可以操作一下。

具体地，假设我们在 处进行了一次操作，我们把接下来的 个元素拿出来，把它们排成 行，每行 个元素的矩阵，那么操作就是插入一整列空数，而接下来我们会移动矩阵，但我们可以快速算出矩阵要移动到哪行，并且只要行对了，我们不需要把 放到第一列

这样我们就能快速执行矩形的移动，使用平衡树维护列的插入，精细实现一下可以发现这个想法是可行的，可以做到复杂度

Holes in Queue 题解做法

Sol

与上一个做法比较类似，但我们不维护一个移动的矩形，而是直接把所有数框进一个矩形

称插入的空数为 ，原来就有的数为 ，初始创建一个只有一列的矩形， 为 ，其余均为

接下来每次操作，操作 时矩形有 列，我们找到 所在的列，在这一列前面插入一个新列，设 的行号为 ，那么这一列 之前的位置都为占位符 ， 到 的位置为 ， 的位置为

此时按照左上到右下的顺序（先右再下，即正常人类阅读顺序）读出所有 ，去除掉所有 ，组成的序列就是我们想要的序列

每一列最多分为三个段，因此总共行只有 种不同的状态，使用平衡树维护，每次需要二分出 的位置

可以发现这个做法非常难写，尽管和上面的做法可能本质相同

复杂度

Balls and Pockets 题解做法

Sol

会改变的情况更复杂一些，看起来我们刚才的方向倒闭了。

返璞归真一下，定义 为 进行一次操作之后会到的位置，定义 为 的逆函数，那么 即为所求

分析 函数的性质，发现元素的移动非常不好描述。

一下操作均指进行一次 ，即把原过程倒过来。

我们产生一个想法：能不能对这些元素分一个段，使得每个段操作完恰好会移动到下一个段，这样迭代 次的时候我们就可以直接定位到答案在哪个段里，然后再想办法段内定位就好了

事实上，这是可行的，我们以 作为第一个段，从这个段开始向后推，满足第 个段的长度恰好等于第 个段内不在 中的位置数量，这样第 个段的元素操作一次之后恰好就到第 个段中所有的非 元素

接下来我们需要解决段内定位的问题，顺着搞虽然有可能可行，但还是比较麻烦，我们倒过来考虑。

选取一个足够大的 ，从 出发，可以发现，我们刚才做的过程相当于不断迭代 ，这样得到的区间都是不交的，我们分的段就和这样得到的所有区间等效

这样我们从后往前移动这个区间，初始维护一个集合 ，每次遇到一个 就相当于将排名为某值的数移除，这个 就相当于求出了函数 表示 在经过足够多次操作，操作到 区间内时操作到了哪个位置

而对于一个询问 ，我们将定位转化为找到对应块中 的位置 ，我们先进行一次定位出 在第 个块中第 个位置，求出 ，我们要找的就是第 个块时 的排名

跑两次上述算法即可，维护可以使用树状数组，复杂度

---

15. QOJ10003 - Decorative Birds [E]

题面

有 只鹅，第 只速度为 ，保证 互不相同，价值为 （可能有负数），且它会在 时刻出现

现在你手里有一些饲料，每当你投放一单位饲料之后此时出现的速度最快的鹅会吃掉这个饲料，提供 的收益，然后消失

你可以随意在任意时刻投放任意多的饲料，你需要最大化收益和

题解

Sol

把所有鹅画到二维平面上，画成 的线段，那么每个时刻可以覆盖到最上面的若干条线段

考虑分开，我们找出所有没选的线段，一定不能有一个选的线段被没选的线段完全盖住

因此我们画出没选的线段的遮挡出的轮廓线（类似直方图），然后对这个轮廓线考虑

我们试图在这条轮廓线上 dp，令 表示轮廓线从左到右延伸到 ，但由于每个区间的长度为 ，所以分析一下可以发现：统计所有左端点不在轮廓线下放，加上向右穿出轮廓线的线段（左半部分在轮廓线内，右半部分不在轮廓线内），就恰好包含所有需要统计的线段

那么我们就直接得到了一个 的算法，轮廓线每次只转移一步。

考虑优化，可以注意到我们只需要处理如下两种转移，其余转移可以直接丢弃：

• 当前横坐标出现了一个线段左端点，这个端点下方的状态转移到在这个端点
• 当前横坐标出现了一个线段右端点，这个端点转移到所有这个端点下放的点

对 扫描线，使用数据结构维护一个 表示 的答案，那么两种转移分别是：

• 求前缀 ，单点修改
• 对 的每个 ，执行

可以使用线段树维护，复杂度

---

16. QOJ8559 - -coloring [E]

题面

给定一张 个点 条边的连通无向图，你需要找一条长为 条边的路径，从 出发，染黑经过的第 条边

最后每条边都要被染黑，给出构造或判断无解

题解

Sol

摘抄一下题解做法。

当 时输出欧拉回路，没有欧拉回路则无解

当 时任意定一棵 dfs 树，输出一个 dfs 序（回边就走过去然后走回来），由于边的两次出现之间差的距离为奇数，所以每条边必定恰好覆盖一次

当 时生成一个 的答案，然后将 的答案四个分一段，设一段是 ，那么我们改成走 ，这样刚好经过了所有偶数边一次

当 时可以从 的答案推过来。

---

17. QOJ8012 - Jumping Lights [E] ✔️

题面

给定一棵大小为 的树，初始所有点均为白色，接下来会发生 次操作，每次操作为以下三种中的一种：

• 0 u，将一个点 染为白色（如果已经是白色则什么都不做）
• 1 u，将一个点 染为黑色（如果已经是黑色则什么都不做）
• 2，对于树中所有点，这个点操作后是黑色当且仅当操作前其所有邻点中至少有一个黑点

每次操作后，求出此时树中有多少个黑点

题解

Sol

可以发现这个操作有类似奇偶循环一样的东西。

不妨 2 操作不会让黑点变成白点，即我们点一个黑色点之后，这个点随 2 操作不断向外扩散

这个我们是可以做的，维护：

• 至少有一个黑儿子的白点集合
• 至少有一个白儿子的黑点集合
• 每个黑点的白儿子集合

一次 2 操作时，我们将所有 内的点染黑，以及将所有 的 集合内的点都染黑，一次 2 操作时我们的复杂度是关于新染黑的白点个数线性的

而 01 操作对这些集合的影响都是 的，因此可以使用哈希表线性维护

但现在有奇偶循环。

我们把树拆成两层，点分别表示为 和 ，且对于每条边 ，将其变为两条边 ，现在我们有一个当前查看的层 ，2 操作时我们将逻辑改为：

• 将 层的点向外扩散一步
• 令

01 操作的逻辑改为：

• 将 在 层的点置为黑/白

但是这样会有一定问题，比如某个点 被设为了黑点，一次 2 操作后它的所有邻居 全都被染黑了，然后我们用 0 操作让 全变白，此时再进行 2 操作，可以发现此时 应该是白点，但是按照我们上面的模式计算会得到 是黑点

这是因为，当层改变时，若此时层为 ，那么我们理应将 层的点全部设为白色，但是出于复杂度考虑，我们并不能这么做

可以注意到上述出问题的情况只有可能是 被染成了一个孤立点的情况，也即我们只需要想办法删除所有孤立点

但是这样的复杂度仍然是不对的：我们可以造一个菊花 连向 ，假设 初始都为黑，进行一次 2 操作后 将变黑，我们把 用一次 0 操作染白，然后再进行一次 2 操作，此时 都应该变白

这意味着我们的均摊分析爆炸了。我们修改的次数可以达到 量级。

我们需要规避这个问题。当我们进行 0 操作时，我们直接将父亲也染成白色，这是对的，因为我们多染一些点不会让答案错误。此时错误的情况就只有孤立点是叶子的情况，也就是上面的 的情况，那么我们把以同一个点为父亲的所有叶子缩在一起，来规避这个问题

那么最后我们的做法为，维护：

• 至少有一个黑儿子的白点集合，按照层分类为
• 至少有一个白儿子的黑点集合，按照层分类为
• 每个黑点的白儿子集合

0 操作时进行：

• 更新上述三个集合，当 为叶子时可能需要精细特判
• 将父亲染黑，将挂在 上的叶子点染黑

1 操作时进行：

• 更新上述三个集合，当 为叶子时可能需要精细特判

2 操作时进行：

• 使用 和 中的点染黑新点

可以发现，01 操作的时间复杂度都是严格 ，并且至多会把 个黑点染白，而 2 操作的时间复杂度关于染黑点数线性

因此总复杂度为

---