第一次在洛谷看见 P1196 的时候我还在背并查集模板。当时觉得这题名字挺唬人——“银河英雄传说”NOI2002打开一看M 指令合并C 指令查询这不是并查集裸题吗结果写完一交WA 得我怀疑人生。直到我把“并查集”三个字拆开不再把它当成背下来的模板而是当成一棵能携带距离信息的树来看才明白标题里那句“树的节点数就是续接树的高度”到底在说什么。这篇东西不打算只给你贴一份 AC 代码而是想把 P1196 从读题到合并的每个细节拆开。尤其是那个让新手最困惑的“续接树高度”问题我会把它讲到你下次遇到同类题时不用回忆也能自己推出来。1. 先把题意拆干净这题不是普通并查集能直接回答的1.1 指令只有两个但查询要的是“相对位置”题目背景不复述核心就两个操作。M i j表示把第 i 号战舰所在的整列战舰接到第 j 号战舰所在列的尾部C i j询问第 i 号战舰和第 j 号战舰之间隔了多少艘战舰。注意这里的用词不是问“是否在同一列”而是问“如果同一列中间夹着几艘”。前者只需要一个布尔值后者需要知道两艘战舰在队列里的具体坐标。这就是普通并查集给不了的东西。普通并查集只维护“谁和谁在一个集合里”节点之间的关系是平等的、无顺序的而这道题的集合内部有严格的线性顺序顺序还随每次 M 操作动态变化。所以我们必须让并查集里的每个节点“记得”自己在集合中的位置信息。1.2 朴素并查集为什么答不了“中间有几艘”用最朴素的并查集实现这道题M 操作用 fa 数组合并两个集合C 操作判断find(i) find(j)。如果相等接下来输出什么你手上只有“同一个根”这个信息你不知道 i 和 j 谁前谁后更不知道中间隔了几个。有人会说那我额外开一个数组 pos存每艘战舰在队列里的下标不就行了问题是一旦发生 M 合并一整列战舰的下标全部要平移。比如把一列 100 艘的舰队接到另一列尾部这 100 艘的 pos 全要加同一个偏移量单次操作就是 O(n)。指令数上限是 500000这么搞必炸。所以单纯靠“给每个元素标一个位置”这条路走不通。必须把位置信息编码进并查集的树结构里让合并和查询都能近似常数时间完成。1.3 把“同一列”升级为“到根的距离”并查集在结构上是一棵有根树每个节点只有一条指向父节点的边。如果我们给这条边赋予一个权值表示“子节点到父节点的相对距离”那么任意节点到根的总距离就等于沿途边权之和。这个总距离恰好可以表示这艘战舰在队列中的绝对位置。于是问题变成在合并和路径压缩两个操作中如何维护这些边权使得任意时刻“节点到根的总距离”都正确。这就是带权并查集也叫边权并查集的经典思路。P1196 是理解这个思路最好的入门题因为它只有“前后顺序”一种关系边权是一个整数合并方向也非常直观。2. 带权并查集的底层逻辑d[i] 到底在存什么2.1 d[i] 的真实含义i 前面有几艘战舰我用d[i]表示节点 i 到fa[i]的距离放到 P1196 的语义里就是“i 前面有多少艘战舰数到它的父节点为止”。这里我们把每列战舰的队首当作根队首的 fa 指向自己d[队首] 0。这样整列战舰就形成了一条链队首是根第二艘的 fa 指向队首第三艘的 fa 指向第二艘……举个例子一列有 3 艘战舰从前往后编号分别是 5、8、2那么fa[5] 5, d[5] 0 fa[8] 5, d[8] 1 fa[2] 8, d[2] 1每个 d 只表示“到父节点这一步”的局部距离。当我们 find 一个节点时沿着父链把 d 累加起来才能得到它到根的总距离。路径压缩后d[i] 直接变成“i 到根的总距离”也就是 i 在队列中的绝对坐标从 0 开始。2.2 为什么不直接存坐标而是存到父节点的距离这是我最初看题解时最大的困惑既然最终要的是每个节点的坐标为什么不直接开一个数组 pos[i] 存坐标非要绕一圈存“到父节点的边权”原因在于合并操作的代价。pos 数组是绝对坐标一旦把一列战舰接到另一列尾部被移动的那一整列战舰的坐标全要改这是 O(列长) 的开销而 d 数组是相对父节点的距离合并时只需要改一个值——被移动的根到新根的距离。其他节点的相对关系没有变它们到各自父节点的 d 完全不用动。等到查询时再通过路径压缩把相对值“折叠”成绝对值。这个“延迟计算”的思路是带权并查集高效的关键也是很多人第一次接触时觉得绕的原因。2.3 用一次 M 操作看懂初始状态到首次合并初始时每艘战舰单独一列fa[i] id[i] 0sz[i] 1。此时每个节点既是根又是唯一的节点。执行M 2 3把第 2 艘所在列接到第 3 艘所在列尾部。2 和 3 各自成列操作后队列是 [3, 2]3 在前。代码上fi find(2) 2 fj find(3) 3 fa[2] 3 d[2] sz[3] 1 sz[3] sz[2] // 变成 2注意这里 d[2] 1 的含义是“2 的前面有 1 艘战舰”正好是新队列里 2 的坐标。再执行一次M 4 2把第 4 艘所在列接到当前列的尾部。这里就有一个初学者必踩的坑4 的根是 42 的根不是 2而是 3。所以代码必须先 findfi find(4) 4 fj find(2) 3 fa[4] 3 d[4] sz[3] 2 sz[3] sz[4] // 变成 3合并后队列从前往后是 3、2、4它们的绝对坐标分别是 0、1、2。验证 d[4] 2正确。这一小节想强调的是合并代码里拿到根之后必须用根来操作而不是用输入时的 i、j。听上去像废话但实际写的时候很多人会因为“反正 find 之后根一样”而偷懒最后整列被拆散。3. 路径压缩的顺序问题先改权值还是先改父亲3.1 递归 find 的标准写法带权并查集的 find 比普通版本多几行核心代码如下int find(int x) { if (fa[x] x) return x; int old fa[x]; // 先记住旧父节点 int root find(old); // 递归找到根 d[x] d[old]; // 累加旧父节点到根的距离 fa[x] root; // 路径压缩 return root; }执行过程先递归找到根回溯时累加 d。因为递归返回后old 是原来的父节点且d[old]已经在递归中被更新成了“old 到根的总距离”所以d[x] d[old]就让 d[x] 变成了“x 到根的总距离”。最后把 fa[x] 直接指向根。3.2 手推一次 find 的执行过程光看代码可能不够直观我们手动走一遍。假设现在有一条链x - a - b - rootfa[x] a, fa[a] b, fa[b] b。调用find(x)old a递归调用find(a)old_a b递归调用find(b)b 是根返回 bd[a] d[b]此时 d[b] 0所以 d[a] 不变还是 a 到 b 的距离fa[a] b返回 b回到 find(x)此时 d[a] 已经是“a 到根 b 的总距离”d[x] d[a]x 到根的总距离 原来的 d[x] d[a]正确fa[x] b路径压缩完成如果换个顺序就全乱了。最常见的错误版本是fa[x] find(fa[x]); d[x] d[fa[x]]; // 错误一旦先执行fa[x] find(fa[x])fa[x] 已经指向根了此时 d[fa[x]] 是 d[根] 0累加了个寂寞。我推荐新手用上面那种“old 变量 先递归再累加再压缩”的写法。虽然多一个局部变量但把顺序固化下来了不容易手滑。等你对这个过程很熟了再去写那种更简洁的版本。3.3 迭代写法的方向陷阱递归版本在 P1196 下最坏递归深度是 30000一列最多 30000 艘绝大多数评测环境没问题。但有些比赛环境栈比较小或者你不放心可以用迭代。迭代版需要先用一个临时数组把路径上的节点存下来然后从根往叶子方向累加。方向很重要不能从叶子往根边找边加。因为迭代是从叶子开始的你先看到的是叶子节点但计算 d[叶子] 需要的 d[父节点] 还没有算好。只有先把路径整段存下来再从靠近根的一端向下处理才能保证依赖的 d 值都已就绪。不过说句实在话如果只是打算法竞赛递归版完全够用。迭代版了解一下原理就好没必要在 P1196 上死磕。4. 合并操作d[fi] sz[fj] 这一行为什么是题眼4.1 size 数组在这里不是优化是队列长度普通并查集合并时size 通常用来做按秩合并优化让树更平衡。但在这道题里size 的角色完全不同——它维护的是队列长度本身。看合并的三行代码fa[fi] fj; d[fi] sz[fj]; sz[fj] sz[fi];第一行把 fi 挂到 fj 下面。第二行让 fi 到新根的距离等于 fj 子树当前的节点总数。第三行更新根节点所在的集合大小。注意不能用sz[fi] sz[fj]因为 fj 才是合并后的根size 只记录在根节点上才有意义。方向写反后面再接新的列时d 值就会出错。还有一点如果 fi fj说明两艘战舰本来就在同一列直接跳过不能执行合并否则虽然 fa 没有实际变化size 却会翻倍整个逻辑就乱了。4.2 树的节点数就是续接树的高度一句话推导现在回答标题里那句话。为什么“树的节点数就是续接树的高度”把每个集合看成一棵树根是队首。fi 是一棵子树的根它要被接到 fj 子树下面。fi 距离它的新根 fj 的“高度”也就是 d[fi]为什么刚好等于 fj 子树的节点数因为队列是线性排的。fj 子树里的每一个节点都排在 fi 子树全部节点的前面。fi 前面有多少艘战舰等于 fj 子树里所有节点的总数也就是 sz[fj]。从树的结构上看就是把一棵大小为 sz[fj] 的树整体放在 fi 上面那么 fi 到根 fj 的距离正好等于这棵树的节点总数。举个例子。fj 子树里有 3 个节点排队是 A、B、Cfi 子树是 D、E。M 操作把 fi 这列接到 fj 尾部新队列是 A、B、C、D、E。D 前面有 A、B、C 三艘所以 d[D] 3 sz[fj]。这不就是“树的节点数就是续接树的高度”么。4.3 其他节点的距离如何“按需”自动正确这是带权并查集最漂亮的地方。假设 fi 子树里有个节点 x原来经过路径压缩后fa[x] fid[x] 表示 x 在旧队列里相对 fi 的位置。执行 M 合并后fa[fi] fj 了但 x 到新根 fj 的距离此时还没更新。什么时候更新等到某次find(x)时才触发。在 find(x) 的过程中递归会先执行find(fi)于是 d[fi] 被更新为 sz[fj]然后回溯到 x 时d[x] d[fi]x 的绝对坐标一次性修正到位。这个过程是“按需”的只要你不查询 x它就保留旧值一查询路径压缩就把它修正。所以多次合并之后每条指令的均摊代价仍然很低。理解这一点你就不会被“合并后其他节点到底什么时候改 d”这个问题卡住了。5. 完整实现与三个让我 WA 到怀疑人生的细节5.1 可以直接对照学习的 C 代码#include bits/stdc.h using namespace std; const int N 30005; int fa[N], d[N], sz[N]; int find(int x) { if (fa[x] x) return x; int old fa[x]; int root find(old); d[x] d[old]; fa[x] root; return root; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); for (int i 0; i N; i) { fa[i] i; d[i] 0; sz[i] 1; } int T; cin T; while (T--) { char op; int i, j; cin op i j; int fi find(i); int fj find(j); if (op M) { if (fi fj) continue; fa[fi] fj; d[fi] sz[fj]; sz[fj] sz[fi]; } else { if (fi ! fj) { cout -1 \n; } else { if (i j) cout 0 \n; else cout abs(d[i] - d[j]) - 1 \n; } } } return 0; }询问时两个节点在同一列它们到根的距离差减 1就是中间隔着的战舰数。比如 d[i] 2 表示 i 前面有 2 艘d[j] 5 表示 j 前面有 5 艘那么 i 和 j 之间隔着 5 - 2 - 1 2 艘。5.2 边界数据自测清单AC 之前一定要自己造几组边界数据对拍。我最常用的几组第一组合并相邻队列。M 1 2 得到队列 [2,1]M 3 4 得到队列 [4,3]M 1 3 把 [2,1] 接到 [4,3] 尾部得到 [4,3,2,1]。查询 C 4 1中间是 3 和 2应该输出 2。第二组连续多次合并后查询跨多个集合的节点。M 5 6、M 7 8、M 5 7此时 5 所在列 [6,5] 接上 7 所在列 [8,7]得到 [8,7,6,5]。查询 C 8 5输出 3。第三组查询 i 和 j 相同输出 0。虽然有的题目数据可能保证 i ! j但加上这个特判不会错。第四组反复执行 M 再 C确保路径压缩后距离仍正确。比如 M 1 2、M 2 3、C 1 3此时队列是 [3,2,1]输出 1。5.3 三个让我 WA 到怀疑人生的细节细节一find 中 d[x] 的累加放在了 fa[x] 被改写之后。这个错几乎每个初学带权并查集的人都会遇到。症状是小数据偶尔正确数据一大就错得毫无规律。解决方法就是记住 3.2 里那个顺序先保存旧父节点递归回来先加 d再改 fa。细节二合并时用了输入节点 i、j而不是根 fi、fj。比如 M 2 4没先 find 就直接fa[2] 4d[2] sz[4]。这样只把单个节点 2 接到了 4 下面2 原来所在列的其他节点全被留在原地整列被拆散。P1196 的合并对象是整列不是单个节点必须先 find(i)、find(j) 拿到整列的根。细节三size 的更新方向写反。合并后必须是sz[fj] sz[fi]。你要是手滑写成sz[fi] sz[fj]当前查询可能勉强正确但下一次把新列接到这列尾部时对方根拿到的 d 就变成小了答案开始全面漂移。6. 从银河英雄传说延伸出去的带权并查集套路6.1 食物链把距离换成模 3 关系POJ 1182 食物链是带权并查集的另一道经典题。里面边权不再是“距离”而是“相对关系”——同类、吃、被吃用模 3 的余数表示。核心套路和 P1196 完全一样d[i] 存 i 到父节点的相对关系find 时按模 3 累加合并时根据已知关系推导根之间的差值。理解了 P1196 里“边权沿着父链累加”的原理再看食物链会发现只是把加法换成了模 3 加法。我当初学食物链时怎么都看不懂那句d[x] (d[x] d[old]) % 3。回头再看其实就是把“前面有多少艘战舰”换成了“与父节点的关系差了几步”累加方式完全没变。6.2 一套通用的思考框架和练习建议带权并查集题有个共同特征集合内元素存在某种可传递的二元关系合并操作把一整棵树接到另一棵树上。遇到这类题按这个框架思考第一步定义 d[i] 表示“i 与父节点之间的某种差值或关系”。第二步推导路径压缩时的转移公式。路径压缩把父节点换成根那么原来的 d[i] 要叠加旧父节点到根的累计值。第三步推导合并时的赋值公式。fi 接到 fj 下面fi 到新根的距离等于 fj 子树对应的累计信息。第四步检查查询时如何利用 d 值还原答案。但凡碰到“合并集合 查询集合内相对关系”的题都可以先往带权并查集上靠。P1196 是这套框架的最小完整样例把这一题吃透后面再遇到核心是“相对位置”或者“相对关系”的题你至少有个非常具体的模板可以参考。最后说句题外话我当年把 P1196 过了之后一度觉得带权并查集也不过如此。直到后来在模拟赛里遇到一道关系要取模、路径压缩顺序又逼着我反复推的题才明白这道题真正教会我的不是那三十行代码而是任何时候都要问自己这个信息在合并之后、路径压缩之后还能不能通过原来的父边权值算出来。想清楚这一点比多刷几道同类题重要得多。