递归回来以后，那条旧路还在

山谷里的路牌会自己认亲。

每个路牌只记下一块内容：下一块路牌是谁，以及到它要走几里。新修的路会把一串路牌接到另一串路牌后面，老路牌不拆，先把新方向写在最上面。

测绘员平时只问两件事。两块路牌是否通向同一个山口。

中间还隔着几块牌子。

某天，他决定把一条弯路抹平。末端路牌原本指向旧父牌，旧父牌又指向山口。

递归从山口回来，末端路牌准备改成直达山口。

测绘员先改了方向，再去看旧父牌。那段路程已经没人替他保管。

地图上的山口还在，距离少了一截。

简化题面

┌─ [P1196] 银河英雄传说
├─ 平台: 洛谷
├─ 题意: 维护若干列战舰，支持把一列接到另一列末尾，并查询两舰之间的舰数。
├─ 输入: 多条操作；M x y 表示合并两列，C x y 表示查询 x、y 的关系。
├─ 输出: 查询时输出两舰之间的舰数；不在同列则输出 -1。
├─ 数据范围: 战舰编号不超过 30000，操作数量不超过 500000。
├─ 关键限制: 合并后需要保留相对位置，路径压缩不能破坏距离。
└─ 完整题面: https://www.luogu.com.cn/problem/P1196

父牌换了，里程不能丢

并查集的父指针只回答方向。带权并查集还要记录到父节点的距离。

合并两列时，把 x 所在列的根接到 y 所在列的根后面：

fa[fx] = fy;
dis[fx] = size[fy];
size[fy] += size[fx];

dis[fx] 是整列平移的距离，等于后面那列原来的长度。

普通路径压缩只关心根。这里必须同时维护距离的语义：dis[x] 表示 x 到 fa[x] 的路程。

返回方向上的旧路

考虑一条三段关系：x -> p -> r。

int find(int x) {
    if (x == fa[x]) return x;
    int old = fa[x];
    int root = find(old);
    dis[x] += dis[old];
    fa[x] = root;
    return root;
}

递归先处理 p。它回来时，fa[p] 已经指向 r，dis[p] 也已经变成 p 到 r 的总路程。

x 还没有改父亲。此刻 dis[old] 仍然是可读取的旧路累计值，dis[x] += dis[old] 才能补齐 x 到 r 的完整距离。

覆盖 fa[x] 以前，旧父节点是最后一块还握着里程的路牌。

两种看起来合理的错法

dis[x] += dis[find(x)];

根到自己的距离为零。这行代码把错误包装成了正确类型。

dis[x] += 1;

只有每条边都长一里时才成立。列车接到另一列后，边权可能是 7，也可能是 7000。

递归函数里还有两个时间点。进入递归前，fa[x] 是旧父亲；递归返回后，旧父亲的距离已经被更新；最后一行才覆盖 fa[x]。

顺序换一下，距离就少一段。

源码里的边界

当前归档实现已在本地编译，并通过四操作样例。训练记录有 AC 结果。

数组初始化仍值得单独检查：数组容量是 N，循环若写成 i<=N，最后一次会越界。旧记录的 AC 不会替当前文件承担这项检查。

带权路径压缩的难点落在“返回以后”。递归返回的瞬间，父节点已经换过，旧边却还留着一份可用的路程。

山谷重新铺路。测绘员把旧路牌擦干净，才写上新的山口。

那条旧路没有消失。它只是换了一个更短的名字。

发布信息草案

• 标题：递归回来以后，那条旧路还在
• 摘要：带权路径压缩必须在覆盖旧父指针前，读取递归返回后已经更新的旧父边权。
• 标签：带权并查集、路径压缩、递归、距离维护