企业官网建设流程全解析

第一次在洛谷看见 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] = i，d[i] = 0，sz[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 的根是 4，2 的根不是 2，而是 3。所以代码必须先 find：

fi = 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 -> root（fa[x] = a, fa[a] = b, fa[b] = b）。

调用find(x)：

1. old = a
2. 递归调用find(a)
   • old_a = b
   • 递归调用find(b)，b 是根，返回 b
   • d[a] += d[b]，此时 d[b] = 0，所以 d[a] 不变（还是 a 到 b 的距离）
   • fa[a] = b
   • 返回 b
3. 回到 find(x)，此时 d[a] 已经是“a 到根 b 的总距离”
4. d[x] += d[a]，x 到根的总距离 = 原来的 d[x] + d[a]，正确
5. 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、C，fi 子树是 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] = fi，d[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] = 4，d[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 过了之后，一度觉得带权并查集也不过如此。直到后来在模拟赛里遇到一道关系要取模、路径压缩顺序又逼着我反复推的题，才明白这道题真正教会我的不是那三十行代码，而是任何时候都要问自己：这个信息在合并之后、路径压缩之后，还能不能通过原来的父边权值算出来。想清楚这一点，比多刷几道同类题重要得多。