本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-02 20:40:40

曹神在校内讲了这个题，并给出了九种做法，标题中的文章也是曹神写的，已严肃学习。

题意

给定 $n$ 个点 $m$ 条边的连通无向图，$q$ 次询问给出 $x,y,z$，求从 $x,y$ 两点分别开始走，共经过 $z$ 个不同点时，经过边的最大编号最小值。

转化后题意：向 $n$ 个点的图中依次加入 $m$ 条边，$q$ 次询问 $x,y$ 两点所在连通块并集大小在哪次加边后超过 $z$。

数据范围：$n,m,q\le {10}^5$，下文均认为 $n,m,q$ 同级。由于关心连通块大小，并查集均使用启发式合并。

概要

提交记录仅供参考，可能实现的比较粗糙。各解法按表格顺序标号。

Sol.1

直接考虑二分，需求出 $mid$ 时刻两点所在连通块及大小。可直接使用可持久化并查集预处理出每个时刻的状态，二分时在上面查询即可。这里给每个点记录一个时间戳 $t_i$，表示该点作为根在 $t_i$ 时刻合并到了别的点上。另外在每个点上开一个二元组序列，记录其为根的连通块点数增加的时间和增加后的大小。由于合并次数是线性的，空间复杂度得到保证。查询 $mid$ 时刻 $x$ 点时先跳父亲直到 $t_x>mid$，再在该点的二元组序列上二分出连通块大小即可。该过程难以路径压缩，只能做到单次 $O(\log n)$。

Sol.2-4

多组询问考虑整体二分，要注意每个元素在每层只能访问线性次，这样才能保证复杂度。此时需求出 $mid$ 时刻每个点所在连通块及大小，有以下三种做法。

Sol.2

直接使用可撤销并查集，用栈维护已进行的操作，并维护当前时刻的指针。处理某个答案区间时将指针移动到 $mid$，过程中进行加边和撤销操作即可，显然指针在每层移动次数是线性的。由于可撤销并查集不能路径压缩，只能做到单次 $O(\log n)$，但该做法常数很小。

Sol.3

考虑按层进行整体二分。具体地，对每层记录所有答案区间，显然其两两不交。从小到大依次处理每个区间，则 $mid$ 一定递增。因此先加入两个 $mid$ 之间的边，再用当前并查集查询即可。由于不需要撤销，可以使用路径压缩做到均摊单次 $O(\lpha(n))$。

Sol.4

据说该做法是青岛地区信息学奠基人 yyc 提出的，因此又称 “yyc trick”。

初始处理答案区间 $[1,n]$ 时，需要知道 $[1,mid]$ 内边连成的连通块情况，这个一遍 DFS 即可求出，左区间 $[1,mid]$ 也可直接递归下去做。问题在于处理右区间 $[mid+1,n]$ 时不能再访问 $[1,mid]$ 内的边，否则递归后复杂度无法保证，因此右区间只能使用 $[mid+1,r]$ 内的边处理。考虑处理完左区间后用 $[1,mid]$ 内的边 DFS 出连通块，并将连通块缩成一个点，带上总点数的权值。之后枚举所有右区间的边和询问，将其 $u,v,x,y$ 均重标号，再递归下去处理。

因此整个过程为：用 $[l,mid]$ 内的边 DFS，处理询问并分到两侧；递归到左区间处理；再次用 $[l,mid]$ 内的边 DFS，用连通块更新权值，并对右区间的元素重标号；递归到右区间处理；将权值还原为更新前的状态。注意缩点时新权值为原权值和而非原点数，还原权值是因为更高层预处理时还会用到原权值。另外为保证复杂度，只能访问 $m$ 条边的 $2m$ 个端点 DFS，其他点默认为单点即可。还要注意每次 DFS 都要清空，总之细节较多，比较难写。感觉实现得确实很粗糙，但还是跑挺快的。

以上四种做法均容易特判 $x,y$ 在同一连通块内的情况，故不再赘述。

Sol.5-7

注意到最优解一定会走最小（瓶颈）生成树上的边，因此考虑建出合并树（Kruskal 重构树）求解。该树从根到叶子权值（原图边编号）$w_i$ 递减，子树内叶子（原图点）数 $s_i$ 也递减。所求即最小 $t$ 使得 $x,y$ 两点跳到 $w\le t$ 的最远祖先后，两子树的并集内叶子数量达到 $z$，有以下三种做法。

Sol.5

直接二分 $t$ 的取值，再用倍增将两点跳到 $w\le mid$ 的最远祖先，求一下当前叶子数量即可。这里若 $x,y$ 在同一连通块内则一定会跳到同一点，容易特判。由于二分和倍增都很满，该做法在所有做法中跑得最慢。

Sol.6

据说该做法是提出了无数 trick 的 gqh 提出的，因此又称 "gqh trick"。

上个做法无法直接倍增是因为两点跳 $2^k$ 步时，所到点的 $w$ 值没有任何规律，难以进行。考虑转为倍增到权值最大的一组不满足 $z$ 限制的点，方法为对 $x,y$ 分别维护倍增位置 $kx,ky$，每次跳到 $x$ 的 $2^{kx}$ 级祖先和 $y$ 的 $2^{ky}$ 级祖先，并统计两子树并集内叶子数量。若已满足限制，则至少有一个点跳多了，因此要求权值较大的点不能跳到，其 $k$ 值减一；若不满足限制，则至少有一个点跳少了或恰好够，因此将权值较小的点跳过去，并将 $k$ 值减一。

这样最终确定 $x,y$ 后，$\min(w_{fa_x},w_{fa_y})$ 即为答案。任意一点往上跳一步就合法是显然的，否则可以跳得更高。然而有时会出现 $w_x>w_{fa_y}$ 这样的情况，但此时答案只取 $w_{fa_y}$ 仍正确。这是因为若 $y$ 没有成功跳到 $fa_y$，一定是因为在 $fa_y$ 时跟另一边已满足限制，且 $w_{fa_u}$ 比另一边大，这样才会强制 $y$ 不能跳上去。因此一定存在以 $w_{fa_y}$ 为较大值的合法方案，$w_{fa_x}$ 也同理，因此这个答案是对的。

过程中有一些细节，比如求两子树并集内叶子数量时，需要特判某点是另一点祖先的情况，此时应只计算祖先点。判断可以预先 DFS 一遍，用 DFS 序判断是否在子树内。另外若某个点已确定，即可只对另一个点倍增完剩下的。这个做法比较抽象，但确实很妙。

Sol.7

与上个做法截然相反，本做法比较暴力。考虑将 Sol.5 中的 $s$ 全放到对应的 $w$ 处，也就是把每个点到根路径上的所有 $(w,s)$ 放到 $w$ 处，并直接对 $w$ 二分，找到两边前缀最大值之和满足限制的最小 $w$ 即为答案。处理方式是维护主席树，每个点从其父亲继承过来，再加入自己的信息即可。二分时由于主席树结构相同，可直接在两棵树上同时二分。

注意特判两个点在同一连通块内的情况，方式是在线段树上维护每个区间对应的树上节点，在上一步二分出结果后取出对应的两个点，判断其是否有祖先关系，没有则答案正确，有则需继续二分出单个值不低于 $z$ 的最小值作为答案。这里从头开始二分即可，前面部分对答案没有影响。

Sol.8-9

考虑只询问单点连通块大小何时不低于 $z$，可以使用警报器。把询问挂在点上，并查集合并时也把所有警报器启发式合并，然后按 $z$ 从小到大检查每个警报是否触发，若触发则该询问答案为当前边边权，删除该警报器；否则后面也不会触发，直接停止检查。这样总检查次数就是线性的了。为了维护从小到大的顺序，需要用 set 或堆维护所有警报，总时间复杂度是 $O(n\log^2n)$ 的。本题需要维护两个点的警报，有以下两种做法。

Sol.8

由于 $s_x+s_y\ge z$ 需要 $s_x,s_y$ 中至少一个不小于 $\lceil \frac z2\rceil$，因此考虑折半，在 $x,y$ 上各放一个 $\lceil \frac z2\rceil$ 的警报，同上进行启发式合并。当两个警报中的一个触发时，将两个警报都删掉并检查，若不合法则令 $z'=z-(s_x+s_y)$，并更新 $x$ 的警报为 $s_x+\lceil \frac {z'}2\rceil$，$y$ 的警报为 $s_y+\lceil \frac {z'}2\rceil$，再放回原位置。由于每次 $z'$ 至多为 $z$ 的一半，至多误报 $O(\log n)$ 次即可得到答案。

注意特判两个点在同一连通块内的情况，方式是在警报触发时先判断目前是否在同一连通块，若已在则转而加入上面说的单点警报器，注意与两点警报器区分。由于每个询问最多同时存在两个警报器，每个时刻警报器总数都是线性的，启发式合并的复杂度不变。该过程可使用 set 维护，由于堆不支持删除任意元素，只能用可删堆代替 set 减小常数，上面表格中的代码使用了可删堆。

Sol.9

考虑优化折半警报器，发现其触发的条件比较严苛，导致必须按值从小到大维护。因此考虑将限制放宽，对 $s_x,s_y$ 找到最大的 $p$ 使得 $f(p,s_x)+f(p,s_y)<z$，其中 $f(p,i)$ 表示大于 $i$ 的数中最小的 $2^p$ 的倍数。将 $p$ 的警报放在 $x,y$ 目前连通块上，在该连通块大小增大过程中经过 $2^p$ 的倍数时触发。增大过程中经过是指 $s$ 增大到 $s'$ 的过程中，存在 $2^p\mid t$ 满足 $s<t\le s'$。警报触发后同样删除、检查，再计算出新的 $p$ 放回去。由于 $p$ 不增，直接不断减小并检查是否合法即可。

现在需要证明误报次数是 $O(\log n)$ 级别的。考虑转而证明一个 $p$ 误报 $O(1)$ 次就会变小，由于 $f(p,s_x)+f(p,s_y)<z$ 且 $f(p+1,s_x)+f(p+1,s_y)\ge z$，因此 $z-(s_x+s_y)\le 2\times 2^{p+1}= 2^{p+2}$，又由于 $s_x,s_y$ 第二次及之后触发警报 $p$ 时均增大了至少 $2^p$，因此同一个 $p$ 触发 $6$ 次时一定求出了答案，即最多误报 $5$ 次。好像可以证明到不超过 $3$ 次，不会。

实现上注意到每次 $s\rightarrow s'$ 时触发的 $p$ 是一段前缀，即 $s,s'$ 不同的最高位及更低的位均会触发。因此在每个点上维护 $O(\log n)$ 组警报，每次触发前缀内的所有警报即可。另外还要求可以删除任意元素，并能以较低复杂度合并。vector 维护启发式合并不能快速删除，因此只能使用链表维护。具体地，每个点的每个组维护一个链表，两点合并时把 $O(\log n)$ 对链表接起来即可，接一对复杂度 $O(1)$，总复杂度 $O(\log n)$。删除也是容易的，只需要记录每个询问的两个警报编号，即可在链表中 $O(1)$ 删除，于是做到了 $O(n\log n)$ 的总复杂度。

注意特判两个点在同一连通块内的情况，同样在触发时先看是否已在同一连通块，若已在则之后的警报都用单个元素的 $f(p,s_x)$ 处理，误报次数同样有保证。细节上要注意在某点上删除后，在同一个点新加入警报不能直接加，而是应该记录下来，等全删完后统一加入，否则可能会出问题。