task20

[TOC]

1. 集训队互测 2025 - Everlasting Friends? [K] ✔️

题面

给定一棵 个点的树 ，定义 分别为以其编号为点权的大根重构树和小根重构树

两问：

• 求有多少非空集合 在 和 上都是连通块
• 求有多少非空集合 在 和 上都是连通块

答案对 取模

题解

第一问

注意到 的所有边在 上都是祖孙边

那么考虑在 上选一个包含根的连通块，我们割掉的边必须满足恰有一条 中的边跨过它，从子树外面到子树内

并且容易发现，只要割掉不互为祖孙关系的一些这样的边，一定合法

因此 求单个根就是所有可以割的边找出，然后跑一遍树上拓扑序，总复杂度

考虑优化对每个根求，注意到一条 中的边 ，一定存在 到某个 子树内的点的 边，并且这条边会一直是可以割的边，直到某个 的祖先再出现一条 边经过了 为止

目前为止已经可以有一个 的 ddp 做法了，但是可以更加优秀

假设我们已经求出了 所有儿子的答案，求 的答案就是在这基础上，把 向下的 边经过的可以割的边全都设成不能割，再把 的儿子边都设为能割

因此我们修改的是一个包含根的连通块，我们实际上就是对于每条被删掉的割边，设其 dp 值为 ，除掉 乘上

这个可以用并查集暴力维护，复杂度除了求逆元之外是 ，总复杂度

第二问

这两棵树没有什么明显的关系了，考虑找一下连通块的性质。

我们把 画到原来的树上，可以发现 在 上也是一个连通块。

这是因为，对于 ，如果 和 路径上没有其它 内的点，且至少有一个不在 内的点 ，那么 想在 上是连通的，则 需要 ，相应的， 如果想在 上是连通的， 需要 ，矛盾

因此不存在这样的 ，任意 的路径上都全是 内的点。

玩一玩可以发现，当我们确定一个连通块的 和 之后，这个连通块就基本确定了，我们只需要 check 一个点集是否满足条件。

那么可以观察一下，可以发现这个确定的点集就是 上 的子树和 上 的子树的交。

分析可以考虑不在连通块内的点对 的限制，对于一个不在 内的点 ，设到 最近的 内的点为

首先在 上考虑，此时 是一个连通块，要么就不能同时有 在 的 子树内，某个 内的点在 的 子树内，这个就等价于 在 的 子树内。

因此要么 ，要么 到 路径上有 的点

类似的，通过另一边的考虑可以得到要么 ，要么 到 路径上有 的点

因此 到 的路径上不能同时没有 的和 的点，这也就是两个子树的交的意思

那么就可以用数据结构刻画了，我们记录 的值，当这个值 的时候说明我们在两棵树上都是一个连通块

考虑在 上扫描，扫到一个点 时，我们维护出对于 上每个点 ，这组子树交的上述值，只有 种贡献点对，每组贡献点对是到根链加，最后我们只需要查询到根链最小值个数即可

dsu on tree 可以做到 ，换成线段树合并可以变为 ，两种做法使用 gbt 均可少一个

---

2. 集训队互测 2025 - 封印 [K] ✔️

题面

给定 ，有 个敌人，每个敌人有属性

对每个敌人，你需要选择一个 ，然后在 的时间中使用魔法封印这个敌人，如果 ，那么封印会成功，你在 时刻会获得 的收益，否则封印会失败，你的收益会在第 时刻清零

任意时刻，你封印的敌人数需要 。任意时刻，你可以选择结束这个过程，此时所有敌人将会消失，即使剩余敌人有封印失败的，你的收益也不会被清零。

求最大收益。

， 为 的排列

题解

Sol

考虑我们的操作是什么样的，假设我们第一次获得收益的时刻是 ，最后一次获得收益的位置是 ，那么实际上我们的要求就是：

• 必须选择所有 内的区间，获得它们的收益
• 必须选择所有左端点在 内的区间，右端点在 外的区间，不获得它们的收益
• 选择一部分左端点在 外，右端点在 内的区间，获得它们的收益

最后所有选择的区间最大覆盖次数不超过 。

可以发现固定 后，需要我们决策的区间相当于全是前缀，因为在 的部分的最大覆盖次数显然不超过 的覆盖次数。因此直接贪心即可，复杂度 .

进一步地发现，我们的贪心过程和 没有什么关系， 一定取到，在算上所有左端点 的区间后，第一次出现覆盖次数 的位置，因此不用枚举 ，复杂度

考虑对 扫描线，优化这个事情，我们维护的实际上就是所有经过 的区间的右端点集合 ，去匹配只考虑左端点 的区间覆盖出来的次数，第一次次数 的位置，第一次次数 的位置，一直到第一次次数 的位置组成的集合 ， 可以匹配当且仅当 ，这个匹配会带来 的收益

而随着我们对 扫描线，我们的修改只有向 或 中加入或删除一个点，这个是可以维护的。

具体地，可以证明对于任意一组原来的最大匹配，我们加入或删除 中的一个点后，一定可以仅通过一次调整得到新的最大匹配，我们开一个线段树，维护 Hall 定理，以加入 的一个点为例，我们首先强行把这个点加到匹配当中，对应到 Hall 定理的线段树上是一段前缀 ，这可能会导致有些位置变为 ，我们找到最靠右的 的位置 ，然后反悔掉一个在 右边的，收益最小的点

其余情况也是类似调整，问题可以在 内解决。

---

3. QOJ14419 - Maximum Segment Sum [K] ⭐

题面

给定 ，对所有 计数有多少长为 的 序列的最大子段和为 ，这里我们认为最大子段和算了空子段，答案对 取模

题解

Sol

求最大子段和的方式是，维护一个变量 ，每次 ，也就是说这是一个可以在 处平着走的格路

但是平着走这个形式非常不好，因此我们进行如下转化：将平面每个横轴的 值从上到下依次视作 ，即在原来的 向下走一步，走到的线代表的意义还是

这样， 的限制就是两条直线了，直接反射容斥即可

总复杂度

---

4. QOJ14713 - Heuristic Knapsack [E]

题面

给定 个物品以及一个容量为 的背包，现在每个物品有一个重量 和价值 ，其中每个物品至多有重量和代价中的一个是不确定的，剩下的数值给定

Alice 会将所有物品按照 从小到大排序，相等则下标升序，然后按照这个顺序，每次若取完背包容量没有超过上限就取

Bob 会将所有物品按照 从大到小排序，相等则下标升序，然后按照这个顺序，每次若取完背包容量没有超过上限就取

求是否有构造方式使得 Alice 和 Bob 取出的物品下标集合相等

，，你构造的 也需要在 内

题解

Sol

这个问题的形式看着很差，所以可以猜测一下我们最后是固定不多的可能的解，然后暴力 check。

考虑进行一些分析：首先，Alice 选择的一定是一段 的前缀

那么，我们把所有 确定的物品都拿出来先排序，枚举 Alice 最后选择了这些物品中的哪个前缀，那么比较容易发现这个前缀内所有 不确定的都应该填 ，前缀外所有 不确定的都应该填

而接下来考虑 确定， 不确定的应该怎么填，将这些按 从大到小排序

可以发现我们要选到答案集合里的一定是一段前缀，否则我们换一下一定不劣

其次可以发现，看起来我们把 从靠后的元素往靠前的元素调也是不劣的，只要靠前的元素的 还是在这个前缀内，因为 Alice 还是会选到，但是 Bob 会在更靠前的位置选到这个 ，因此更有可能把别的不属于答案集合的物品“挤掉”

因此如果确定了最后我们选出的答案集合之和 ，我们把 已经确定的从 里面减掉，剩下的顺着扫 排序的前缀，每次尽可能多给当前元素分，这样就是正确的

最后，我们说明 一定尽可能大，因为同理，我们给一个元素的 加 一定更有可能把不属于答案集合的物品“挤掉”

因此我们对每种 前缀，我们选取 前缀的方式是固定的，那么暴力 check 即可

但是出题人心地险恶， 的最大值可以达到 ，此时需要再多写一些特判。我懒得说是怎么写的了，感觉没有什么营养。

复杂度 或

---

5. AGC074D - Valid Output for DSU Problems [E]

题面

按照如下方式生成一个 01 串 ：

有一个 个点的图，初始没有边，创建一个大小为 的操作集合，集合中有两种操作：

• 对于所有 ，有一个在 之间加一条边的操作
• 对于所有 ，有一个查询 是否联通

你需要重排所有操作，然后根据每个询问操作是否连通生成一个长为 的 01 串

现在给定 ，以及一个长为 的 01 串 ，求最少交换多少次相邻项能将 变为一个可能被生成出的

题解

Sol

假设确定了加边的顺序，那么每一种询问都是前面的一些时刻为 0，后面的一些时刻为 1，我们要判断的是能不能生成某个 01 串

可以发现，我们顺着扫，每遇到一个 1 一定取当前最早变为 1 的，而如果倒着扫，每遇到一个 0 一定取当前最晚变成 1 的

那么有了这两个直觉，我们就可以发现我们将所有询问按照变为 0 的时间排序，假设有 个 ，那么最后作为 1 的询问一定是前 个，作为 0 的询问一定是后 个，并且顺着扫 的每一个元素，我们取的是最靠前的那种答案的询问

因此，可以发现，设 变为 0 的时间是 ，那么在选到第一个时间是 的 1 询问之前，我们一定要选完所有的时间为 的 0 询问

也就是说，设我们边数变化依次为 ，那么找到满足 的那个位置，第 个 0 的位置要比第 个 1 的位置靠前

有了这个限制之后，我们直接枚举 到 ，设其合并的两个连通块为 ，再枚举剩下 个点形成的边数 ，我们就是从 变到了

枚举了 之后，计算答案就是固定第 个 1 和第 个 0，最少多少次操作让第 个 0 在第 个 1 之前，这个容易预处理之后 计算

那么我们就得到了一个 的做法。

把它优化到 就是枚举 和 ，然后我们只要让 为一个尽可能大的 的数即可

---

6. EGOI2025 - Wind Turbines [E] ✔️

题面

给定一个 个点 条边的无向连通图，边有正整数边权

次询问，每次给定一个区间 ，查询将 内所有点之间两两连 边之后最小生成树的边权和

题解

Sol

显然对于原图我们可以只保留最小生成树上的边。

而连一些边之后意味着我们会断掉一些原树上的边，那么我们对于一条边考虑它什么时候会被断掉

经过一些思考，我们可以发现，设 内的点为关键点，那么这条边 会被断掉当且仅当 的两边各存在一个关键点，到它的路径上边权都小于 的边权

那么我们建出 kruskal 重构树，这个对应的就是这条边两个子树中均有 内的点

启发式合并求支配点对即可，总复杂度

---

7. QOJ970 - Best Subsequence [E]

题面

定义一个序列的 -权值 为：

选出这个序列的一个长为 的子序列 ，最小的 的值

次询问，每次给定 ，求 子区间的 -权值

题解

做法 1

Sol

考虑如何求一个序列的 -权值，我们二分一个 ，判断在 的情况下最多能选多长的子序列

这个可以贪心：从小到大贪心选数，假设当前扫描到了 ，找到前后第一个选了的数 和 ，若 ，那么就加入这个数，容易发现这是对的

可以发现如果不考虑环的情况，那么一个数的前驱和后继都是固定的

而截出来一个区间的时候，会因为是环出错的只有前缀最大值和后缀最大值，那么我们把前后缀最大值单独处理

对 整体二分，预处理区间内非前缀最大值的可以通过二维数点处理，前缀最大值/后缀最大值可以从 开始倍增，每次找下一个大于/上一个小于的位置，我们要找到的就是把所有前后缀最大值拿出来按值排序之后，极长的前缀使得相邻两项的和均

这个可以找到第一个 的位置，然后 check 一下第一个 的位置

check 一次复杂度 ，总复杂度

做法 2

Sol

求一个序列的 -权值还是二分一个 ，然后从小到大扫描依次加数

但是这样不方便计算，原因也是做法 1 中提到的前后缀最大值的问题

那么我们忽略这个问题，直接按一个数 是否 作为合法标准，允许这里的 和 选到外面

可以发现，非前后缀最大值计算的一定是正确的，而前后缀最大值可能多算一些东西，但是可以发现，算出来的和答案的差不超过 ，因为前缀最多算错一个 的，后缀最多算错一个 的

因此我们可以通过线段树上二分找到一个算出来的 与实际需要的 很接近的 ，在这个基础上再进行 次调整即可得到解。

---

8. QOJ10872 - Kid’s Game [E]

题面

给定一个 的字符矩阵，每个字符是 GZDPX 中的一种，两个人在上面博弈

如果一行相邻两个元素依次为 GZ，先手可以将其改为 DP

如果一列相邻两个元素依次为 DP，后手可以将其改为 GZ

不能操作者输，若游戏会无限进行则平局，求游戏结果

题解

Sol

把 G 变为右箭头，Z 变为左箭头，D 变为下箭头，P 变为上箭头

可以发现，所有箭头要么在右下之间切换，要么在左上之间切换，因此这样可以串出来若干个阶梯状的链，链之间互不影响

而对于每条链，我们可以视作有左箭头和右箭头，先手可以操作所有奇数位置上的 RL，后手可以操作所有偶数位置上的 RL

可以发现，我们直接计算每个链操作到 LLLLLRRRRR 为止先手比后手多操作的次数加起来如果 就是先手胜，否则后手胜，因为通过一些简单的分析可以得到后手无法操作的时候，每条链的 先手-后手 都是 的，所以这样不会判错

那么直接计算即可，复杂度

---

9. IOI2023 - Closing Time [E]

题面

给定一棵 个点的树，边有边权，你需要给每个点分配一个非负整数权值

定义一个点 能到达点 ，当且仅当对于 到 路径上的每一个点 ，都有

给定两个特殊点 ，求在所有 的和 的情况下， 能到的点数加上 能到的点数最大是多少

题解

Sol

显然每个 只会取 或者

如果 能到的范围和 能到的范围不交，那么是容易的，把每个点的 拿出来，贪心地取前若干小即可

否则， 到 路径上必须全都选了 ，那么每个点要么是：选了 就 ，要么是选了 就 ，选了 就再

这个可以用反悔贪心实现，复杂度

---

10. IOI2023 - Longest Trip [E] ⭐

题面

交互题。

有一张隐藏的 个点的无向图，满足对于任意三个不同的点 ， 三条边中至少存在一条

现在初始给定 ，你可以向交互库提出询问，每次询问你需要给定两个不交非空点集 ，交互库会返回 到 之间是否有边

现在你需要在不超过 次询问内求出这张图任意一条的最长简单路径

题解

做法 1 (85pts)

Sol

考虑维护一条链，每次我们加入一个点 ，让 判断和链头链尾是否有连边，若有，我们直接将 加入到链中，否则，说明这条链首尾之间一定有边，也就是说这个链一定是一个环

那么我们只要找到任意一个和 有连边的点，就可以再串成一条链

显然可以通过二分找到一个有连边的点，但是这样的点有可能不存在，并且这样的操作次数也过多

因此我们需要多设计一些状态，具体地，最后可以使用如下三类状态：

• 已知一条路径串起来当前加入过的所有点
• 当前加入的点不连通，不难发现这种情况下两个连通块一定分别是团，我们求出这两个团的点集 分别是什么
• 已知一条路径串起来当前加入过的所有点，并且我们知道两个已经加入过的点 ，满足 之间没有边

对于第一种状态，我们加入一个点 的时候可以询问 分别与链头链尾是否有连边，若有，则可以加入链中，若没有，我们询问加入这个点与原来的图是否有任何连边，有则二分出连边，转为第三种状态，否则转为第二种状态

对于第二种状态，加入一个点 的时候可以通过询问这个点与 是否有连边可以确定 向 有连边或者向 有连边，再询问 到不确定有连边的另一个集合是否有边，有则二分出来，转为第三种状态，否则保持第二种状态

对于第三种状态，加入一个点 询问其与链头和链尾是否有连边，若有，再判断一下是和哪个有连边，若没有，则链是一个环，此时由于我们已知 没有连边，因此 和 中至少有一对有连边，再用一次询问确定即可，保持第三种状态

对于所有不涉及转状态的加入操作，我们都使用 次询问，一到三和二到三 分别使用 次操作，一到二使用 次操作

因此总操作数为

做法 2

Sol

没有什么思路，因此我们首先尝试询问所有 和

注意到若 均没有边，那么 必定有边

因此我们可以尝试改进一下这个策略，维护一个链的集合 ，我们最后期望得到的效果每个 链尾和 链头都没有连边，并且除了 和 ，其余的链都长度

可以发现 ，那么我们可以尝试想办法用 次操作完成上面的事情，再用 次操作合成一条链，就可以做到 次操作

用 次操作完成上面的事情是可以做到的：时刻维护 的链尾和一个可能存在的与 链尾没有边的点 ，新加入一个点 的时候：

• 如果 不存在，直接询问 链尾和 ，根据是否有边选择将 加入 或者作为新的
• 若 存在，询问 和 ，如果 和 有边，将 作为新的链，否则将 加入 末尾

可以发现，这样我们得到的 是 级别的。

将这些链合并在一起就比较简单了：当链数 时，找到前三条链 ，询问 链头到 链尾和 链头的哪个有边，不管哪个有边都可以连成一条新的链，注意到合并完之后可能不满足 链尾到 链头没有连边，但是我们不需要用到这件事情

最后两条链的时候查询一下是否有连边，如果没有直接输出，如果有的话再进行一些讨论，容易在 次操作内求出最终答案

因此我们一共需要 次操作

---

11. IOI2023 - Soccer [E] ⭐

题面

给定一个 的网格，每个格子都有可能是障碍

现在求面积最大的四联通区域，使得其不包含任何障碍，且对于其中任意两个格子 ，存在一条从 到 只经过区域内的点的路径，最多拐一次弯

题解

Sol

肯定要找充要条件，不难发现一个必要条件是区域连通且是“凸”的，即每行每列占据的格子都是一个区间

除此之外，可以发现任意两行的区间应该有包含关系，否则分别在两行的差集内取一个格子，这两个格子将无法拐一次弯到达

结合这两个条件之后，可以发现这是必要的。

那么我们可以列出 ，从外到内每次剥掉最小的区间，但是剥区间不是很舒服，我们可以倒过来，从最宽的行往外转移，转移到两边

令 表示当前区域占据了 之间的行，且所有 或 的区间必须被 包含，转移可以把 往里缩，或者向 或 扩展一行

那么我们就得到了一个 的做法

可以注意到，我们的 一定是扩展到一个极大的在 行内全是空白的区间，所以有效状态只有 个

进一步地，可以发现向 或 扩展一行这件事情一定是能做就做，因此我们实际上有效状态是 是一个极大空白矩形

可以分析出来这样的状态只有 个：固定 之后向右推，每遇到一个障碍就像是笛卡尔树那样把矩形裂开，因此对于一个 只有 种合法的状态

而这些状态我们可以记录成：选择一个 ，从这个位置开始向右找，找到第一个障碍 ，然后把 这个范围尽可能向上向下扩展，得到的矩形

现在我们的状态是 的了，转移只需要枚举是动 还是动 ，如果动 就是从 转移，否则就是从上下两个边界上最靠左的障碍转移，都是容易预处理的

总复杂度

---

12. QOJ12305 - Permutasino [E/K] ⭐

题面

给定一个长为 ，值域为 的数组 ，请选择 个 的排列 ，每个排列分配一个权值 ，满足

题解

乱搞

把 排序，注意到一个必要条件是前 小的 之和

那么我们可以猜测这个条件是充要的。

这个可以看成，数轴上我们有 个点初始在 ，接下来我们需要把这些点向内挪，即选择两个点 ，把 加 ，把 减

那么考虑初始选 ，可以视作我们在 分别放置了一个点，我们要把这些点移动到某些特定的位置，接下来我们不断把 调整成别的排列，这个过程可以视作有一些点在以一些速度向左或向右运动

我们选择一个排列，一直移动直到有一个点到了特定的位置为止，这样重复 次即可将所有点归位，使用排列数不超过

但是如何选择排列——我们选择的排列需要满足如下事情：

• 首先，我们不能把合法的序列操作到不合法
• 其次，我们的速度要足够，即我们总共使用的时间不能超过

最后我使用的策略是，将向右的点视作 (，向左的点视作 )，对于每一个极长的 (((())))))) 段，设左右括号数量分别为 ，将排列构造为对 ，将第 个左括号和第 个右括号对换

这样看起来在随机数据下不会出现上述两个问题，所以通过了。

Sol

由于必要条件是前 小的 之和

那么考虑如果存在一个 满足前 小的 之和 ，此时我们可以对前后分别构造出来解，然后将它们合并在一起

设我们构造出来的解满足前面的排列等于 ，后面的排列等于 ，其中 分别为 和 的排列， 为系数，满足

我们可以通过打擂台，一开始取 拼起来一直选，直到 用完了或者 用完了，然后用对应序列的下一个接替

这样匹配出来我们会使用 个排列

但是对于原问题，我们不一定有这样的一个

因此我们考虑，任选一个排列 ，设这个排列的系数为 ，我们取 ，可以发现对于任意 ，一定存在一个 的取值使得这个序列满足上述条件，且有一个合法的

这个 可以二分求出，然后就可以递归子问题，总时间复杂度 ，瓶颈在于合并两个子问题的答案

---

13. QOJ11723 - I’ve Got Friends [E]

题面

给定一张 个点 条边的无向图 ，请构造 个二元组 ，使得对每个 ，，且 和 之间存在边当且仅当 ，或者判断无解

题解

Sol

摘抄一下 std 做法，我的做法太垃圾了。

题目即给定一个无向图，要求构造一张图使得给定图是它的线图。

首先我们去除重边，可以发现如果有两条边相邻，并且它们的邻边集一样，那么一定存在构造使得它们两个互为重边，因此缩掉即可

可以证明，当一个连通图 满足 时， 对应着一张唯一的 （同构的图算作相同）

那么考虑增量构造每个连通块，每次选择 的一个顶点，满足这个点与之前的至少一个点有边，然后：

• 若 ，暴力找任意合法的图，当加入后有五个节点时，我们恰好能构造出唯一合法的图
• 否则，判断是否能新加一条边使得这条边的邻边集是对的，如果邻边集都和一个点相连，那么将新边与这个点相连，另一端与一个叶子相连，如果邻边集都和两个点相连，且这两个点之间没有边，那么直接连起来
• 其余情况无解。

复杂度

---

14. QOJ11722 - Hamilton [E]

题面

有一个 个点的无向图，对每个 ， 和 之间连了一条边权为 的边，且对于任意 ，且 ， 和 之间连了一条边权为 的边

给定 ，构造一条 到 的边权和最小的哈密顿路，或者报告无解

题解

Sol

不妨假设 。

可以发现，奇偶性有一定意义，因为如果 都为奇数，且 为偶数，那么根据奇偶个数分析即可得到无解。

这个题看起来答案如果很大的话就不好做了，因此我们看看能不能找到一些边权和比较小的方案

而用 中转的话，有可能造不出来方案。

那么我们增加一个点，同时用 中转，可以手玩一下所有情况可以发现这时必定有解，且这个解可以

而解 的时候，我们一定是在三段之间跳两次，也就是说我们每次跳到的一定是段的端点

那么把 拿出来去重跑 dp 即可

复杂度

---

15. ULR3 - Again Counting Stars [E]

题面

给定一个长为 的数组 ，有一个光标初始位于位置 ，满足 ，你可以进行以下两种操作：

• 将 加 ，然后
• 将 减 ，然后

过程中需要满足 ，但不需要满足

最后需要满足 回到原位，，对初值 求解 ，对 取模

题解

Sol

不难发现和不变。手模一下，可以发现我们一定是把一些值向右挪，那么求前缀和，把一个值向右挪的操作就相当于是给前缀和数组单点

而额外地，这个光标的形式限制我们的前缀和数组改变的一定是一段包含 的区间，因此对于一个 ，我们统计的实际上是满足如下的序列个数：

• ，
• 所有满足 的 组成一个区间，要么这个区间为空，要么这个区间包含

如果没有第二个限制，我们可以使用容斥，将一些 容斥成 ，这时 的限制就是容易的了，只要求一个下降幂即可，容易做到 dp

现在要求区间包含 ，我们转为容斥，减去区间完全在 左边或者完全在 右边，那么我们就要对每个前缀求出答案

改一改上面的 dp，在合适的位置给 dp 初值 ，仔细讨论一下转移即可，对于后缀也可以做

总复杂度

---

16. ULR3 - 成王败寇 [K]

题面

给定一棵 个点的字典树，称第 个节点代表的字符串为 ， 次询问，每次询问给定一个节点 ，以及 个限制 ，求有多少节点 ，满足：

• 是 的后缀（可以为空）
• 对每个 ，若 ，那么 的第 个字符应为

题解

Sol

建出 fail 树，对每次询问，考虑分情况讨论，设最大的限制是 ，设阈值 ：

• 若 ，直接暴力 check 所有这样的串
• 若 ，找到这些 对应的第 个字符，由于 ，那么这些节点子树大小至少有 ，因此这样的子树不超过 个，对每个子树数一下内部有多少在 的 fail 树祖先上的点即可，这个可以在 fail 树上 dfs，然后用 平衡的分块维护

总复杂度

---

17. ULR3 - 我的 XOR 卷积人生 [K]

题面

交互题。实现一个程序，能对两个下标为 的 矩阵序列 求解如下序列：

$$c_{U}=\sum_{S\oplus T=U}a_Sb_T$$

，要求复杂度

题解

Sol

考虑位运算卷积的更深刻理解。

我们可以把每一位都看成一个形式元 ，那么我们已知所有 ，我们想要求出 ，直接考察 ，对比一下可以发现我们原来的算法相当于取了 和 代入，这时 ，我们再用这些点值插回一个一次函数，得到的就是

同理，对于 OR 卷积，这个就是 ，也就是我们取 和

但是现在 没有逆元，我们解不了这个方程，考虑把它变成 ，取 ，最后我们再令

这个也可以将其平移为 ，然后解决：

$$c_A=\sum_{S\cup T=A}a_Sb_T2^{|S\cap T|}$$

最后再平移回来，这个式子可以通过子集卷积处理，还是加一个辅助 popcount 维

复杂度

---

18. QOJ14942 - Buggy Painting Software II [K]

题面

通信题。

给定 ，交互库会给定 个数 ，保证 ，Alice 需要给每一个 分配一个长为 的数组，这个数组中 各出现恰好三次

交互库对每个数组，选择一个 的真子集 ，然后将数组中的每个数，若其在 内则替换为 ，否则替换为

Bob 会收到这 个操作之后的数列，Bob 需要对每个数列，还原出这个数列一开始对应的

题解

Sol

考虑先将所有数组的 位置填为 ，这样我们就可以得到 是什么，那么我们就是要选出 个长为 的串，使得对于任意一个集合 ，这 个数组中 中的数的位置组成的集合两两不同

如果 是质数的话，我们直接填 的循环位移即可

但问题在于 不一定是质数。

注意到上面这个解告诉我们的事情是对于一个质数 ，任意长为 的不为全 或全 的串，它的循环位移一定两两不同

那么我们在 之间找到一个质数 ，任意在这 个元素内填入 ，保证 都出现至少一次，然后把这个串循环位移即可

解码可以使用 kmp 或哈希。

---

19. CSP-S 2025 - 员工招聘 [E]

题面

有 个人来应聘，你有一个长为 的 01 串 ，且每个人有一个忍耐值

这些人会按照某个顺序来依次应聘，第 天每天恰有一个人来应聘，如果第 天的 ，则这个人会被拒绝，否则这个人会被录用

此外，对于一个人 ，如果在它之前已经有 个人没有被录用或者放弃应聘，那么它也会放弃应聘

给定常数 ，求有多少应聘人的顺序使得能录取到至少 人，答案对 取模

题解

做法 1

Sol

显然我们需要按照天数考虑，否则 非常难处理

假设我们依次决定每天有没有录取人，那么每天的要求相当于 或者任意

注意到 是不断增加的，那么我们在 增加的时候考虑所有 的人的去向，此时， 限制的位置已经都必须填完，而 也一定转变为了任意的限制

表示前 天，一共 个人没有被录取，且前面有 个任意限制的位置还没有使用（从这个信息可以推算出当前我们有多少 的数没有用）

转移仔细讨论一下。

做法 2

Sol

依然是从前往后考虑每天有没有录取人，那么每天的要求就是 或

我们把 容斥成任意减去 ，然后设 表示前 天，有 个人被拒绝，且我们钦定了 个任意

转移也可以讨论做到 ，总复杂度

---

20. NOIP2025 - 树的价值 [E] ⭐

题面

给定一棵 个点的有根树，保证树的高度不超过

请在每个点上填一个非负点权，最大化每个节点子树 mex 之和

题解

Sol

考虑固定每个点最后的子树 mex，我们判断是否能达成

那么考虑从下往上填数，假设我们已经满足了每个儿子的 mex，现在要满足 的 mex

此时 mex 有可能不够，不够的话我们就可以用子树还没有使用的节点把 mex 补满

而注意到此时我们找到 mex 最大的子树，如果这个子树还有没有使用的点，那么我们在补 mex 的时候会扩大这个子树的 mex，所以这种情况显然不是最优的

那么对于每个点 ，这个点的 mex 就等于它 mex 最大的儿子 ，加上其它儿子用来补这个点 mex 的点数

我们把一个点的指向它 mex 最大的儿子的边看成实边，那么实边就组成了这棵树的一个链剖分

而对于每个点 ，它最后会在它的某个祖先处被当作补 mex 的点，那它补的这个 mex 就会贡献向上实边连续段长度的系数

也就是说，我们需要选定链剖分，然后每个点的价值为：祖先中最长的实边连续段的长度，我们要最大化这个价值和

那么就容易写出一个 的 dp 了： 表示节点 ，祖先中最长实边连续段长度为 ，当前实边连续段长为 ，子树的价值和最大值，转移显然是 的，总复杂度

考虑进行优化，首先我们把状态变为 ：令 表示节点 ，祖先中最长实边连续段长度为 ，并且当前实边连续段长度也为 ，再定义辅助状态 表示节点 ，祖先中最长实边连续段长度为 ，并且当前实边连续段长度为

的转移可以容易的表示成 ，而 的转移需要快速跳过一段长为 的实边链， 的转移需要我们在 的子树中选一个节点 ，满足 ，然后贡献 加上路径上所有其它儿子的 之和

我们除了求这个值的部分都是 的，而求这个值可以对每个 用长剖优化

因此总复杂度

---

21. NOIP2025 - 序列询问 [E] ⭐

题面

给定长为 的整数数列 （可以有负数）

次询问，每次给定 ，你需要对 求出来对于所有长度在 中且包含 的区间， 值区间和的最大值

题解

Sol

显然我们需要求前缀和。

那么画到二维平面上，横坐标为 ，纵坐标为 ，我们要查询的就是一个梯形内的最大值

首先可以发现我们容易 查询一个矩形内的最大值，这就是两次区间求前缀和最大值

而注意到，对一个梯形我们可以进行如下处理：

当 的时候我们可以用两个这样的平行四边形覆盖整个范围，而每一个平行四边形就是一个滑动窗口 rmq

而对于一般的情况，我们有多种处理方式：

• 如果 ，其中那么 中一定有 的次幂，设其中的 的次幂依次为 ，那么 和 一定都是 的区间，而 的答案我们可以预处理，即初始处理出 的答案，然后区间取 max

• 将左下角的蓝色三角用这三种图形拼起来：

  

  每种图形都可以直接求

最后复杂度 ，预处理复杂度 或

---

22. CTT2025 - 异形工厂 [K] ⭐

题面

给定长为 的 01 串 ，一步操作你可以将 任意长为 的子串向前或向后循环移动一位

次询问，每次询问给定 ，求只保留 和 的情况下，在 上操作多少次能让它变为 ，或者判断无解，询问之间独立

题解

Sol

画一下操作可以发现相当于我们可以把一个 移动一位或两位，那么从 变到 就是做边权为 的最大匹配

这是出现过的问题，没出现过也可能可以得到贪心做法：

• 我们从左到右扫，假设此时前缀 中的 比 中的 多，维护一个待匹配的桶，下标为奇偶性，如果当前 ，那么就在 的桶中放入一个 ，如果 ，就尝试从 的桶中取出一个 ，如果没有了就从 的桶中取出一个 ，进行匹配，否则 ，什么都不做（其实也相当于两件事情都做了）

可以发现，这个其实就等于，第 个 中 和第 个 中 的位置差之和，再加上我们被迫从 的桶中取出一个 的次数，再除以

将 的值画成折线，那么询问区间的起点终点必须是同一高度，设这个高度为 ，那么可以发现，这个折线切到 的高度的若干次，就把这个折线划分为了若干个独立的段

那么我们只要对每个点 ，预处理出 到下一个与 高度相同的位置这个区间的答案，最后全部相加即可

预处理的时候，我们考虑把向上（^）和向下（v）的两种分别预处理，对于其中一种，我们使用栈从左到右维护扫，扫到一个位置时，我们栈中会储存若干个还没有完全求出的区间，对每个区间我们直接维护它们的奇偶桶

可以发现，对于栈中所有的区间，奇偶桶中奇数是递降的，偶数也是递降的，那么我们在这上面进行的操作就是（不妨假设 的个数比 的个数多，也即折线形如向上 ^）：

• 如果 ，那么就是给 桶全部
• 如果 ，那么就是 桶 的区间全部 ，然后 桶 的区间，给 桶 ，容易验证操作完之后两个桶还是分别递降的

两个操作都是可以用树状数组维护的，再额外开一个树状数组维护栈内区间的答案

总复杂度 ，代码很好写。

---

23. IOI2023 - Beech Tree [K] ✨

题面

给定一棵 个节点的有根树，根为 ，每个不为根的点有颜色

称一棵树是绝妙的，当且仅当存在一个其节点的重排 ，使得 是根，且我们按照如下过程能得到和这棵树完全一样的树：

• 依次考虑 ，如果 在 中出现了 次，那么 的父亲是

求这棵树每个子树是否是绝妙的

题解

Sol

同一个颜色的点的父亲一定组成了 的一个前缀

因此，这意味着两个颜色的父亲集合必定为包含关系，这可以等价表述为一个点的儿子颜色互不相同，且任意两个点的儿子颜色一定为包含关系

但是这仍然不是充要的，考虑接着强化我们的条件。

注意到如果 排在了 前面，那么对于一个颜色 ，如果 都有 儿子，设其为 ，那么 也要排在 的前面，也就是说 的儿子集合是 的超集

这样推下去，我们可以发现如果 排在 的前面，那么 子树一定“包含” 的子树

此时可以发现，这就是充要的，我们将所有子树拿出来，那么大小相等的子树应该完全一致

每次我们将一个大小最大的子树排在最前面，并且如果 在 前面，那么对于任意颜色 ， 的 儿子一定在 的 儿子前面，可以发现这样显然不会出环，并且构造出来的排列满足对于每种颜色 ，它们的父亲一定按照前缀的顺序排列

因此，我们已经得到了一个可以检验的判据，即将所有子树按照 排序之后，应该形成一个包含的链

注意到判断包含关系我们只要判断子树 大于等于即可，因为如果整个序列满足条件，那么 大于等于就等价于包含

而求每棵子树是否绝妙，只要启发式合并 序列，然后每次额外判断新的相邻项是否包含即可

复杂度

---

24. QOJ11630 - Simple APSP Problem [E] ⭐

题面

有一个 的网格，上面有 个障碍，你需要求对于所有 种选出两个非障碍格子的方案，将它们的最短路（一步可以向上下左右移动）相加求和，对 取模

题解

Flamire 做法

Sol

考虑将网格缩起来，对于一段极长的没有障碍的行将其看为一个整块，一段极长的没有障碍的列将其看为一个整块，最后形成一个由块形成的矩阵，矩阵一共有 个块

可以猜测一下，两个块内任意点对之间的最短路，在块矩阵上经过的块都是一样的，画一画可以发现这个非常有道理

进一步发现，如果一行或一列是多行合并出来的，那么我们显然不会跨过这个行/列两次，因为这行/列是完全空的，这确实没有什么意义。

因此，我们可以总结，两个块之间任意点对的最短路比 多的步数，就等于两个块在块矩阵上的最短路上比 多的步数

以每个块为起点跑一下 bfs，然后用二次函数求和即可 计算两个块之间所有点对的最短路之和

复杂度 。

题解做法

Sol

本质相同，但是比上面更好的表述。

对于两个相邻的空行，任意最短路显然不会经过这个行两次，因为这是一个空行。

那么我们可以直接给答案加上上面的白格子数乘上下面的白格子数，然后将这两个空行缩起来，直接成为一个空行（空行中的格子带一个统计答案时的次数）

最后会缩成一个 的矩形，从每个白格子开始跑 bfs 即可，复杂度

---

25. APIO2025 - Road Closures [E]

题面

给定一棵 个点的树，边有边权

对每个 求断掉一些边使得剩余的点最大度数 ，断掉的边的最小权值和

题解

Sol

当 时这个是原树的最大权匹配

注意到对每个 ，度数 的点的个数之和是 的，因为每个点会恰好被算度数次

因此我们考虑对这个做一些事情。

注意到对于一个度数 的点，它连出的所有连到度数 的点的边，我们断掉的一定是一个前缀

那么我们把所有度数 的点之间的边拉出来，在这个上面 dp

令 表示 子树都已经填完， 向上的边有没有删

转移容易做到

复杂度

---

26. APIO2025 - Rainforest Jumps [E] ✔️

题面

给定一个长为 的数列 ，保证 互不相同

如果你当前在 ，你可以跳到左边第一个满足 的 或者右边第一个满足 的

次询问，每次给定 ，求从 内的任意一个点出发，跳到 内任意一个点的最小步数，或者判断无解

题解

Sol

原来的做法有点烂，这里介绍一个干净一点的做法。

对于一个区间 ，找到其中最大值 ，区间中的点一定都在 的子树里

那么我们找到 中的最大值 ，显然我们的出发点也要是 子树内的，因为我们每一步跳都是在移动到笛卡尔树上的祖先

由于 的子树也是一个区间，所以我们把这个区间和 取个交，会得到一个新的出发区间

在 内找到最大的位置 ，可以证明这是最优的起点： 内所有点都在 的子树内，那么从其它点开始跳一定不如直接从 开始

那么接下来我们需要解决的就是一个点到一个区间的问题

设 中最大值是 ，那么我们大致从 开始，在笛卡尔树的链上不断向上跳，直到跳到 内为止

可以发现我们一定是尽可能想跳到左右两边更高的那个的，仔细讨论一下我们的跳的过程，设 跳更高的下一步跳到的是 ：

• 如果 的值 ，那么一定直接跳过去
• 如果 的值在 内，那么如果 已经在 内，一步走过去即可，否则从 再向右走一定走到 内，只需要两步
• 如果 的值 ，那么 一定是向左跳，此时我们只能一直向右走，走到 内

这些都可以倍增优化，总复杂度

---

27. THUPC2026 初赛 - 覆盖游戏 [K] ⭐

题面

有一个 的矩形格，每行每列恰有一个障碍

你需要用 个横条和竖条覆盖所有非障碍格，且不能经过障碍格

求覆盖方案数量，我们认为 的横条和竖条是不一样的，答案对 取模

题解

Sol

趣味。

可以发现这个 应该是最小的。但是为什么是最小的呢？这个证明应该能对我们做这道题有启示作用。

注意到极长的非障碍横条竖条一共有 个，也就是说有一半的这些横条竖条应该满足，这个横条/竖条内，我们没有填进去一个方向相同的横条/竖条

如果我们把填横条竖条看作给每个格子填横向还是竖向的话，这个意思就是有 个极长横条/竖条的格子都只填了相反方向，称这样的情况叫做不被指向

可以发现这个限制很强，因为我们直接确定了一个极长横条/竖条的方向，并且根据抽屉原理，至少有一个障碍格子有大于等于三个方向不被指向，那么我们对这样的障碍格进行讨论：

情况 1：存在一个黑格任何方向都不被指向

此时这些方向已经至少需要 个条来填了，因此答案至少为

情况 2：存在两个黑格，只有一个方向被指向

手玩一下，可以发现可能的情况只有上图，以及其对称情况

那么设两个黑格中间有 列，图中所有横向的箭头至少需要扩展出 个横条，但中间 列，每列至少有一个障碍，因此会将这些横条再断开 次，也即横条至少有 个

而竖条一共至少有 个，加起来刚好是

情况 3：有小于等于一个黑格，只有一个方向被指向

此时至少有 个长条

因此我们证明了至少需要 个长条才能覆盖所有非障碍格

而接下来考虑如何计数，我们显然只用考虑情况 1 和情况 2：

• 情况 1：方案数可以拆成四个角，分别延伸的方案乘起来

• 情况 2：中间 列的已经确定，必须是延伸到不能延伸为止，而四个角上也是类似的独立问题，可以拆开乘起来

现在我们就是需要解决形如：左边界上有一些横向长条，下边界下有一些竖向长条，我们需要延伸这些长条覆盖这个区域内的所有非障碍格子

观察得到下图：

即：

• 所有障碍必须是从左下到右上的，否则两个障碍会挡出一个无法被我们覆盖的格子

• 我们画出分割横条和竖条的边界线，可以发现这是一个从左下到右上的折线，并且经过每个障碍格子的右上角

  但这不是完全一一对应的，如果我们经过了一个障碍的左下角，从两边走到这个障碍的右上角都对应着同样的分割方案，减掉即可

那么我们就可以成功递推出每个格子右上角的方案数

重复若干遍，然后按照之前的计算方式乘起来即可

复杂度

---

28. APIO2022 - Mars [E]

题面

一个下标为 的矩格，每个格子可能是陆地或者水域

你需要设计一个机器人，求出陆地四连通块数

机器人的磁盘里有一个 的数组，每个元素都是一个长为 的 01 串 ，初始 表示对应格子是陆地还是水域，其余为止全部为

这个机器人按照如下方式操作：

• 首先，循环 ，计算
• 对于每一个 ，依次处理

其中，处理一个格子 的意义是：

你会将 这九个格子的 01 串 放到内存里，然后你需要仅根据内存里的信息，以及当前的 做出一些决策，最后给 赋一个新值

你需要进行所有操作之后，使得 中的值从高到低组成的二进制数，恰好是陆地的四连通块数

题解

Sol

在第 轮时，我们只使用 这些格子

我们采用如下策略：做完一轮的时候，我们用 存下所有 格子的信息，然后每个 存下所有 格子是否是障碍，每个 存下所有 格子是否是障碍

对于 ，可以发现我们需要存的信息是：

• 右下角轮廓线上每个非障碍格子的等价类情况
• 没有碰到轮廓线的连通块个数

第二个信息显然只需要 个 bit，考虑如何在比较少的 bit 内传输第一种信息

注意到将轮廓线展开成一维后，等价类形成一个类似于括号序的东西，因为不能有两个连通块交叉

那么我们随便写出一个可能的序列：

1 0 2 2 0 2 0 3 0 2 0 1 0 0 4 0 1

一种思路是将所有格子指向下一个与它同等价类的格子的边传输过去，而由于我们是括号序列，所以只需要传每条边的起始点和终止点

但是如果我们每一个位置都是 ，那么总共需要传 的信息，这不是很好，因为

那么我们想办法提前传一些信息，比如我们对于让除了 之外的信息格，传两行/两列，即所有 传 是否是障碍， 传 是否是障碍

这样相当于我们已知了每个位置是零还是非零

1 0 2 2 0 2 0 3 0 2 0 1 0 0 4 0 1
1 0 1 1 0 1 0 1 0 1 0 1 0 0 1 0 1

而注意到每个连续非零段一定属于同一个等价类，并且每个连续非零段的下一个一定是 0

因此我们可以将每条边的出发点移动到这个非零段后面的 0，这样每条边的段点，如果在 0 的位置，那么一定是起始点，如果在非零的位置，那么一定是终点，那么我们只需要传每个位置有没有端点即可：

1 0 2 2 0 2 0 3 0 2 0 1 0 0 4 0 1
  o------------------>o o------>o
        o>o o---->o
0 1 0 0 1 1 1 0 0 1 0 1 1 0 0 0 1

这部分我们使用了 个 bit，完全足够

最后通过这些信息即可还原出整个图的连通块数

---

29. APIO2025 - Game [E] ⭐

题面

一个 个点的有向图， 为关键点，初始对每个 都有 的边，除此之外没有其它边

次加边，强制在线，加完每条边之后你需要回答是否存在一个环包含至少一个 内的点

题解

Sol

容易将环上不包含非关键点的情况判掉

首先有一个显然的 做法：设 表示 的点中能到达 的最大编号， 表示 能到的 的点中的最小编号

那么对于一个非关键点，如果 ，说明我们存在了一个环

加入每条边的时候更新 和 ，由于值域为 ，所以只会被更新 次，总复杂度

而当 的时候，相当于我们要时刻判断是否存在 的路径，我们看起来只能开始从 和 分别开始搜，那么我们的做法似乎避免不了这样的东西

对 的链，我们将其分为两半 和 ，称这两半分别为 集合和 集合，只要有 的路径就爆了

称能到 的集合为 ，从 能到的集合为 ，那么 和 必须不交

如果不交，那么相当于我们知道了不存在跨过 的环，也就是说我们只要考虑 和 各自内部有没有环

而注意到， 上如果要形成环，环上的点必定都属于 ，因为环上的点都能到 内的点

也就是说，我们可以将这个问题分治成两个问题， 的子问题点集为 ， 的子问题点集为

接下来考虑如何在这个结构上支持修改：

当我们加入一条边时，我们会扩大 和 集合，集合依旧不能有交，否则立刻有环

而扩大集合会导致子问题的点集变大，也即多了一些边属于子问题，那么我们就在子问题上再运行加边操作，递归进行

注意到一个点以及一条边只会被下放 次，因此总复杂度是 的

但是直接实现空间复杂度可能带 ，需要精细实现优化到线性或者优化常数

其实下放点的过程就是我们先将 区间放到一个线段树节点上，然后需要下放的时候就是这个节点的 已经完全属于了左子树或者右子树

所以从这个方向上可能比较好实现？这样实现出来应该和洛谷题解区的线段树结构做法差不多？

总复杂度

---

30. QOJ11627 - Rectangles [E]

题面

给定 ，请求出有多少种方案，用 的小长方体堆砌满一个 的 torus-长方体，答案对 取模

题解

Sol

称 ，可以证明一定整除，否则无解。

手模一下二维情况，可以发现这样一定是要么是每 行一组，一组内以任意行循环位移排满 长方形，要么是 列一组，一组内以任意列循环位移排满 长方形

但三维情况不一定是这样的。

首先，如果填满三维的方案可以在 中的某一个方向上剖成 个二维的问题，称这样的填法是“平凡”的

计数所有“平凡”填法是容易的，只要容斥 这三个方向上分别可不可以剖即可

接下来计数非平凡填法。

我们考虑 的横剖图，这会形如一个二维的问题，只不过每个 矩形此时同时还有一个 的颜色，表示其在 轴上 的余数

显然不会有长方体跨过两个 余数不同的位置，那么也就是说我们能进行的操作只有在每一种余数内部对长方体填的方式进行重排

而非平凡意味着我们有一个井字一样的结构：

....##....####.......
....##....####.......
#####################
#####################
....##....####.......
#####################
....##....####.......

其中 # 表示一个余数相同的区域（除了 # 之外还有可能有别的余数和其相同的格子，但它们没有组成整行整列，所以不影响我们重排的方案数）

我们枚举 表示这些行对应了多少个 ，列对应了多少个 ，使用巨量分讨可以算出方案数

需要额外求系数 表示 的方格填入 的颜色，且不存在任意一行或一列全 的方案数，这个容易 处理

总复杂度

---

31. CEOI2025 - Boardgame Expo [E] ⭐

题面

给定一个 个点 条边的无向图，请将 划分为若干个连续区间 ，使得每个 的导出子图连通

求划分区间数最小的一组方案

题解

Sol

容易观察到解是唯一的：我们最后回答的区间应该满足对于任意 ，不存在一个其它 使得 ，而如果两个有交区间是连通的，那它们的并也是连通的

注意到如果原图是一棵树，那么我们可以使用线段树维护点减边容斥，动态维护出所有区间是否是一个连通块

考虑从左往右加点，时刻维护所有区间的联通情况。

再额外注意到，当考虑到 时，对每条满足 的边 赋权 ，只保留最大生成树上的边不影响每个 是否是一个连通块

那么我们只要能维护出最大生成树的变化，就可以调用之前的算法解决这个问题

这个可以使用 lct，但我不会 lct，所以我使用了整体二分，相当于二分出每条边存在的时间区间，这个仔细讨论一下，可以用整体二分+可撤销并查集做到

总复杂度 ，使用 lct 则为

---

32. CEOI2025 - Theseus [E] ⭐

题面

通信题，有一张 个点 条边的无向图，其中某个点 为终点

Ariadne 会得知这张图，以及终点 ，她需要给每条边赋一个 信息

接下来，Theseus 会从图上某一个点 出发，试图走到 ，任意时刻，如果他当前处在 ，那么他会得到 的编号， 所有邻居的编号，以及 向所有邻居连边的信息

他需要根据这些信息，选择一个出边走过去，走过去之后他将忘记他在上一个节点得知的任何信息，也即他选择出边的判断只能根据他在当前节点能看到的信息进行

请构造一种策略，使得 Theseus 移动的步数 ，其中 ， 为 到 最短路的边数

题解

Sol

注意到操作就是给边定向，因为我们可以用 信息传递是小连向大还是大连向小

求出每个点的最短路，我们最好的打算就是让每个点想办法指向一个最短路比它小的

但是这并不是总能办到，具体来说，一层内的点可能有很多很多内部的连边，我们没有明显的方式让它们选择向上一层连的边

考虑一些情况：

• 团：每条边从大连向小，所有 的邻边都连向 ，让每个点走向它指向的点编号最小的出边，那么所有点都会先走到 ，再走到
• 注意到我们一层内的点，势必要某些点的 增加 ，但是我们能造出一个树一样的结构，给每一个当前层的点下面挂上任意的图，因此看起来我们需要对 增加的点需要有一定选择性，特别地，我们可以期望找到一个类似于启发式合并的过程

有了上面的启发，我们设计一个过程：

从 大到小处理每一层，让走的人总是走指向的点编号最小的出边，如果我们已经处理完了 的所有点，每个 的点下面都会挂一棵子树，表示有多少下面的点按照这个策略走最终会走到它，称这个大小为

我们按照 从小到大考虑，每次找到 最小的点 ，将其所有向 的出边向外连，这样连完之后，找到这个点会选择的那个编号最小的出边，设其走到了 ，那么如果 就一切都好，否则给 加上 ，对 进行动态更新

容易发现这样我们造出来的边，每走一次同层的边都会让 乘以 ，因此每个点移动的步数

---