第一次见《银河英雄传说》这道题是在集训队的一本老题集上当时只觉得“NOI2002”几个字分量十足。后来自己动手做了一遍又拿它给学弟学妹讲过好几轮才真正意识到这道题在并查集教学里的地位——它几乎是“带权并查集”最经典的入门模型也是把“树高”“路径压缩”“维护距离”这几个概念揉在一起讲的最佳载体。先说一句大白话并查集是干什么用的它的核心回答是“两个元素在不在同一个集合里”但很多实际问题不光要回答“在不在”还要回答“离多远”。银河英雄传说问的就是这个“离多远”——两艘战舰中间隔着多少艘战舰。裸的并查集只维护父子关系回答不了距离把并查集的每条边走一条“边权”让每个节点记下到父节点的距离问题就迎刃而解。这就是很多人常挂在嘴边的“树高”“带权并查集”也是这篇博客想彻底讲清楚的东西。这篇内容适合所有正在学并查集的算法初学者也适合刷过题但没完全理解距离维护逻辑的选手。我会从并查集最基本的作用讲起再一步步推演到带权并查集把 P1196 的思路拆开、揉碎最后给出完整可提交的代码和这几年我见过最多的几个坑。1. 先弄明白并查集到底是用来做什么的网上搜“并查集主要用来做什么的”你会发现回答五花八门但说来说去都绕不开一件事把一堆元素按关系分成若干组并快速判断任意两个元素是否在同一组。这个“组”可以是朋友圈、可以是网络里的连通块、可以是地图上的省份也可以是银河里的战舰队列。并查集之所以叫“并查集”是因为它只干两件事合并集合、查询归属。底层数据结构是一棵棵多叉树每个集合用一棵树表示树的根节点就是这个集合的代表元素。判断两个元素是否在同一集合只看它们的根节点是不是同一个。int find(int x) { return fa[x] x ? x : (fa[x] find(fa[x])); }这段代码是路径压缩版本的 find几乎是所有并查集实现的地基。你没看错就这么几行它就能支持几百万元素的合并查询操作。原理也简单查找 x 的根时沿途经过的所有节点直接挂到根下面下次再查它们就是 O(1) 的跳转。但如果你只想做“在不在同一个集合”这种判断普通并查集就够了。真正让题目变复杂的是类似银河英雄传说这样的场景——同一个集合内部还要分先后顺序、还要算相对距离。这时候就需要给并查集的边加上“权值”于是有了带权并查集也叫“边带权并查集”。强调一个容易被忽视的点题目标签里的“树高”通常有两种理解。一种是按秩合并里那个“树的高度”为了控制复杂度另一种就是在带权并查集里维护“节点到根的距离”这个距离本质上就是节点在树上的“高度权值”。银河英雄传说里两个概念都会用到但核心是第二种。1.1 并查集的三个基本操作不管功能怎么扩展并查集始终围绕三个基本操作展开初始化每个元素单独成一个集合自己就是根。查询 find(x)找 x 所在集合的根节点顺带路径压缩。合并 merge(x, y)把 x 所在集合并到 y 所在集合或者反过来。对应到代码就是void init(int n) { for (int i 1; i n; i) fa[i] i; } int find(int x) { // 路径压缩 if (fa[x] ! x) fa[x] find(fa[x]); return fa[x]; } void merge(int x, int y) { int fx find(x), fy find(y); if (fx ! fy) fa[fx] fy; // 把 x 的根挂到 y 的根下面 }有经验的老选手会再加一个sz数组做按大小合并把节点少的集合挂到节点多的集合下面进一步压低树高。但要注意如果题目对合并方向有硬性要求按大小合并就不能随便用。银河英雄传说就有这个限制稍后细说。1.2 树高在并查集里的角色树高这个指标在普通并查集里主要影响复杂度。一棵树如果退化成链表find 每次都要跑 O(n)那就和暴力没有区别。路径压缩和按秩合并都是为了压低树高让 find 接近 O(1)。而在带权并查集里树高有另一层含义它是“节点到根的距离”是查询答案的关键数据。你维护的d[x]表示 x 到父节点的距离经过路径压缩后d[x]就变成了 x 到根节点的距离。这样两个节点之间的相对距离就能通过它们的d值做差算出来。银河英雄传说中的战舰队列本质上就是一串节点排成一条链。合并一个队列到另一个队列末尾时被移动的队首到新队首的距离恰好等于另一个队列当前的战舰总数。这就是d[fx] sz[fy]这一行的由来也是整道题的精髓。2. 从暴力模拟到带权并查集思路是怎么一步一步长出来的我们先把题意翻译成人话一开始有 30000 列每列只有一艘战舰编号 1 到 30000。接下来有最多 500000 条指令指令分两种M i j把编号 i 所在的整列战舰接到编号 j 所在的战舰队列末尾。C i j询问编号 i 和编号 j 的战舰之间隔了多少艘战舰。如果两艘战舰不在同一列输出 -1。第一次看到“把整列接过去”这个操作第一反应是模拟。用一个二维数组或者链表维护每列的顺序合并的时候整块搬动。但数据范围一出来模拟就凉了30000 列500000 次操作光是搬运数组元素就可能达到千万甚至亿级别稳稳超时。那有没有更聪明的办法只需要想清楚一个关键问题我们真的需要维护整列战舰的完整顺序吗不需要。查询只问“两艘战舰之间隔了多少”也就是它们的相对距离。为了得到相对距离我们不需要知道中间具体是哪些战舰只需要知道它们在队列里的“坐标”。如果把每列战舰看成一条链队首是链头那么每艘战舰的“坐标”就是它到队首的距离。两个坐标一减再减一就是中间隔着的战舰数量。这时候思路就通了用并查集维护“在哪一列”这个连通关系再额外维护每个节点到队首根节点的距离。合并操作相当于把一棵树接到另一棵树的根下面同时更新被移动子树根节点的距离。这就是带权并查集。2.1 裸并查集为什么回答不了距离问题先写一个裸并查集试试fa[x] 只记录 x 的父节点find(x) 只能告诉你根是谁。合并 M i j 的时候把 i 所在树的根接到 j 所在树的根下面这条边没有任何权值树的结构也完全是一个黑盒。之后查询 C i j只能得到“是同一列”或“不是同一列”。是同一列的时候距离等于多少裸并查集完全不知道。因为你没有保存任何节点在树中的位置信息也无法从 fa 数组还原出节点之间的相对位置。换个角度说裸并查集丢掉了顺序信息。原本战舰队列是有前有后的但你只保留了“谁属于哪棵树”不保留“谁站在谁的后面多远”。因此单纯在裸并查集上打补丁是行不通的必须额外维护距离数组。2.2 重点距离数组 d 和集合大小数组 sz 的设计带权并查集需要在普通并查集基础上增加两个数组d[x]x 到fa[x]的距离。路径压缩之后d[x]会更新为 x 到根的距离。sz[x]x 作为根节点时所在树的总节点数。只有根节点的 sz 是有效的非根节点的 sz 不用维护。以银河英雄传说的合并为例M i j 执行时找到 i 的根 fx 和 j 的根 fy。把整列 i 接到列 j 的末尾等价于把 fx 放到 fy 的下面并且 fx 到 fy 的距离应该是 fy 这列当前的战舰总数。于是fa[fx] fy; d[fx] sz[fy]; sz[fy] sz[fx];到这里“树高”的概念就立起来了。本来 d[x] 是 x 到爸爸的距离合并之后 fx 成了 fy 的儿子所以 d[fx] 被赋予新值。查询任意两艘战舰的距离只要对 d 值做差就能得到。这里有一个很容易滑过去的坑合并方向是固定的。M i j 是把 i 所在列接到 j 所在列后面绝对不能让 fa[fy] fx。否则战舰的顺序就反了查询结果会错得莫名其妙。这种方向敏感也是带权并查集和普通并查集最大的区别之一。2.3 为什么说路径压缩在本题中是必须的如果不做路径压缩find 操作每次都要沿着父链往上走。虽然合并方向固定但多次合并之后树高可能达到几万500000 次操作累积下来最坏情况会退化到 O(nm) 级别TLE 没跑。路径压缩在这里还有一个额外的好处它能在查找过程中顺带把 d 值累加正确。看这段代码int find(int x) { if (fa[x] x) return x; int root find(fa[x]); d[x] d[fa[x]]; return fa[x] root; }递归先找到整条链的根回溯时 d[fa[x]] 已经被更新成 fa[x] 到根的距离那么d[x] d[fa[x]]就自然完成了“沿途累加”的工作。回到银河英雄传说里这就意味着每次 find 之后d[x] 直接变成了 x 到队首的真实距离查询时直接取值即可不用再额外遍历。有同学会问路径压缩会不会改变树的结构导致距离信息丢失不会。并查集合并的本质是把树根连起来路径压缩只是把某个节点从树的中部直接挂到根上它到根的距离在原树中已经确定压缩时通过累加父链距离得到之后依然保持正确。3. 核心代码逐行拆解一个能 AC 的带权并查集模板说了这么多原理是时候动手写代码了。我先把完整代码放出来再逐段解释。这是 C 实现属于最常用的写法加上快读可以过 500000 条指令的数据范围。#include bits/stdc.h using namespace std; const int MAXN 30005; int fa[MAXN], d[MAXN], sz[MAXN]; // 初始化每艘战舰单独成一列 void init() { for (int i 1; i MAXN; i) { fa[i] i; sz[i] 1; // 每列初始只有一艘战舰 d[i] 0; // 自己到自己距离为 0 } } // 查找 路径压缩 距离累加 int find(int x) { if (fa[x] x) return x; int root find(fa[x]); d[x] d[fa[x]]; // 回溯时累加父节点到根的距离 return fa[x] root; } // 合并把 x 所在列接到 y 所在列末尾 void merge(int x, int y) { int fx find(x); int fy find(y); if (fx fy) return; fa[fx] fy; d[fx] sz[fy]; // fx 到 fy 的距离就是 fy 列当前的长度 sz[fy] sz[fx]; } // 查询返回两艘战舰之间的战舰数量 int query(int x, int y) { int fx find(x); int fy find(y); if (fx ! fy) return -1; return abs(d[x] - d[y]) - 1; } int main() { ios::sync_with_stdio(false); cin.tie(0); init(); int T; cin T; while (T--) { char op; int i, j; cin op i j; if (op M) { merge(i, j); } else { cout query(i, j) \n; } } return 0; }3.1 初始化细节d 和 sz 的初值不能错初始化时每个节点单独成列所以 fa[i] isz[i] 1d[i] 0。这个“d[i] 初始为 0”容易被忽略但必须写。原因很简单在路径压缩的版本里每个节点的 d 值最终要累加到根如果初始 d 不是 0路径压缩时会多出一段无中生有的距离整个查询结果就全乱了。3.2 find 的递归顺序为什么先递归再累加int root find(fa[x]); d[x] d[fa[x]];这段代码顺序是精心设计的。递归会一层层进入直到根节点。回溯时父节点到根的距离已经算好存在 d[fa[x]] 里这时再把父距离加到当前 d[x] 上就得到了 x 到根的距离。如果调换顺序先d[x] d[fa[x]]再递归那 d[fa[x]] 还没更新成到根的距离累加的就是错误值。这个细节我见过不少新手翻车所以特意拎出来说。find 结束前fa[x] root把 x 直接挂到根下。以后再次查询 x只需要一次跳转这就是路径压缩的威力。3.3 merge 的合并方向和 sz 更新顺序merge 里面最容易犯的错是写反方向。正确逻辑是fx 是 i 所在列的队首根fy 是 j 所在列的队首根把 fx 接到 fy 后面所以 fa[fx] fyfx 到 fy 的距离是 fy 列目前所有的战舰数量也就是 sz[fy]更新总数量sz[fy] sz[fx]注意 d[fx] 的赋值用的是 sz[fy] 的旧值也就是合并之前 fy 列已有多少战舰。必须先取旧值赋给 d[fx]再更新 sz[fy]。虽然实际顺序调换也能算出正确答案因为赋给 d[fx] 的只是那一个数值sz[fy] 之后变大不影响已赋的值但逻辑上理解成“旧长度”更清晰也更不容易写错。另外如果 fx fy说明两艘战舰本来就在同一列合并操作不需要执行。虽然题目数据通常不会出现这种情况但健壮性还是要的。3.4 查询答案时为什么减一query 先判断两个根是否相同不同直接返回 -1。相同的话d[x] 和 d[y] 分别表示它们到队首的距离差的绝对值就是两者在队列中的位置差。但是位置差是“相隔的段数”战舰之间的空隙数是“相隔舰船数量”两者差 1。举例子队列是 1、2、3、4d[1]0d[4]3位置差是 3但 1 和 4 中间只隔着 2、3 两艘战舰。所以答案等于 3 - 1 2。写 query 时如果忘了减一样例输出的所有正确答案都会偏大 1这个 bug 极为隐蔽尤其容易在自测数据恰好差值很小时被漏过去。3.5 性能说明与快读补充500000 条指令每次 find 在路径压缩后都接近常数总复杂度近似 O(T · α(n))完全没有压力。我用 ios::sync_with_stdio(false) 提速一步到位。如果环境限制不能用这个也可以手写 getchar 快读但没必要。4. 调试经验这些坑我当年都踩过说实话带权并查集不看题解第一次写对的人真的不多。它不是那种“语法错了”的难而是逻辑上差之毫厘谬以千里的难。我把这几年带学生遇到最多的几个问题整理成了一张速查表现象可能原因解决办法答案总是偏大 1query 忘了 -1确认位置差减一合并后距离不对fa[fx]fy 写反成 fa[fy]fx检查合并方向距离时对时错find 里先累加后递归必须先递归回溯再累加初始化忘写 d[i]0答案多了初始距离初始化补上 d[i]0不同列输出 0 而不是 -1没判 fx ! fy加判断4.1 坑点一递归版 find 在极端树高下可能爆栈路径压缩之后树高一般不会太高但如果你前期合并操作非常密集递归层数在最坏情况下仍然可能达到几万层。虽然 C 默认栈空间通常够用但在某些在线评测环境下500000 次递归调用依然存在风险。更保险的写法是循环版 find。不过需要注意非递归写法维护 d 值时要先记录路径上的所有节点再逆序累加。代码会比递归版长不少对新手不那么友好。我的建议是先用递归版把逻辑理解透实测 AC 后再考虑要不要改成非递归版。4.2 坑点二二次压缩后 d 值的维护容易写错在一些复杂题解里你会看到 find 写成这样int find(int x) { if (fa[x] x) return x; int tmp fa[x]; fa[x] find(fa[x]); d[x] d[tmp]; return fa[x]; }这里用一个临时变量 tmp 保存旧的父节点然后递归更新 fa[x]最后 d[x] 加上旧父节点到根的距离。这种写法和d[x] d[fa[x]]在逻辑上是一样的区别只是用临时变量规避了“递归后 fa[x] 已变”的顾虑。实际测试中两种写法都能 AC但如果你对递归时序不太熟用 tmp 版本更不容易出错。4.3 坑点三按秩合并不能乱用普通并查集优化里按秩合并是个好习惯把矮树接到高树上。但在银河英雄传说里合并方向被题目写死了M i j 必须把 i 列接到 j 列后面。要是为了压树高强行“把矮的接到高的上”舰队的相对顺序就乱了查询结果直接错。所以“树高”这个标签在本题里不是让你按秩合并而是让你维护节点在树上的深度距离。这是我见过最多的一个误解也是很多讲题视频没有点透的地方。可以用路径压缩保证复杂度但不能随意改变合并方向。4.4 自测数据的构造方法样例过了不等于能 AC。我建议自己构造几组边界数据来验证第一组M 1 2、M 3 4、C 1 4结果应该是 -1检验不同列判断。第二组M 1 2、M 2 3、C 1 3队列是 1 2 3答案应该是 1。第三组连续多次 M比如 M 1 2、M 1 3、M 2 4手动模拟队列顺序后验证 C 1 4。第四组同一列查询自己C 1 1答案应该是 0绝对不要输出 -1。边界数据出问题往往说明 d 值在多次合并中累加错了这类 bug 比逻辑错误更隐蔽但构造好测试用例后定位很快。5. 从银河英雄传说延伸开去带权并查集还能做什么银河英雄传说只是带权并查集的入门款。这类题有一个通用套路d[x] 维护的可以是距离可以是数量也可以是模数下的偏移量。最著名的扩展题是“食物链”POJ 1182三类动物构成环形捕食关系用 d[x] % 3 表示 x 与根的关系。每次合并时x 到 y 的关系要通过根节点中转本质上就是一边做路径压缩一边维护模运算下的权值。思路会比银河英雄传说绕一圈但底层逻辑完全一致把两个根之间的关系通过 d 值推导出来。另一个常见方向是离线查询的区间关系。比如问你一系列“前缀和”相关的相等或不等条件是否矛盾本质上也是并查集节点带权维护相对差值。学会了银河英雄传说再去看这些题会轻松很多因为你已经习惯了“并查集 额外数组维护相对信息”这个组合。5.1 我常用的思考套路总结遇到一个题目怀疑是并查集但不知道是不是带权版本可以按这个顺序想这个问题的关系是否具有传递性比如“在同一列”是传递的a 在队列 Xb 在队列 X则 a、b 必然在同一队列适合并查集。除了连通性是否需要知道集合内部元素的相对位置或相对关系需要的话必须上带权。合并操作是否对方向有要求有要求就不能随意按秩合并必须用路径压缩保证效率同时额外维护 d 数组。d 数组存什么单位距离、数量、模数、差值取决于题目。这个套路帮我在比赛中快速判断算法选型。写题写多了你会发现带权并查集题目的难点从来不是代码而是能不能在 10 分钟内把“权值”定义清楚。5.2 一道题啃下来之后还能做什么如果你只是为了 AC 这道题那本文的代码已经足够。但如果你想彻底掌握这个方法我建议做两件事一是把递归版 find 改成非递归版并把两种写法的正确性都验证一遍。这个过程能帮你彻底理解路径压缩时的回溯顺序。二是尝试不看代码只用 d、sz 两个数组的语义从零推导一遍合并过程和查询公式。能推出来说明你真的理解了而不是背下了题解。就我个人的体会而言银河英雄传说这道题最迷人的地方在于它用最朴素的方式让你看到“并查集”这个看似只能回答 0/1 的数据结构只要加上一条边权就能回答任意两个节点间的距离。很多高级算法本质上都是在基础结构上多维护一维信息这个思维习惯远比某一道题的 AC 更重要。