必须用按秩合并+可持久化数组（主席树）存fa和dep，禁用路径压缩；因路径压缩每次find会触发O(log n)次单点更新，导致O(n log² n)时空开销，TLE/MLE。

不能靠路径压缩，必须用按秩合并 + 可持久化数组（主席树）来存 fa 和 dep 两个数组。否则一做路径压缩就会爆炸式产生新版本，内存直接爆掉。

为什么不能用路径压缩

路径压缩在 find 过程中会递归修改沿途所有节点的 fa[x]。每次赋值都触发一次可持久化数组的单点更新，而一次 find 最坏改 O(log n) 个点，n 次操作就可能生成 O(n log n) 个新节点——空间和时间双双失控。

• 普通并查集里路径压缩是“免费”的，因为原地改数组；可持久化下每次改都是“新建版本”
• 可持久化线段树单次单点修改是 O(log n) 时间 + O(log n) 空间，路径压缩把它放大成 O(log² n) 级别
• 洛谷 P3402 的数据范围（n, m ≤ 2×10⁵）下，路径压缩版基本稳 TLE/MLE

必须维护两个可持久化数组：fa 和 dep

每个版本的并查集状态由两个数组共同决定：根节点靠 fa 向上跳，合并策略靠 dep 判断谁挂谁。这两个数组必须独立、同步地可持久化。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

• fa 数组：记录每个节点当前父节点，初始化为 i（即自己）
• dep 数组：记录以该节点为根的子树深度（不是高度），只在两棵树 dep 相等时才让一方 dep++
• 合并操作 union(x, y) 必须先 find 出两个根 rx, ry，再按 dep[rx] 和 dep[ry] 决定谁当新根
• 所有 find 都只能迭代/递归向上跳，不能压缩，返回的是当前版本下真实的根

回滚到第 k 个版本的本质是切换 root[k] 和 dep_root[k]

所谓“回滚”，不是撤销操作，而是把当前使用的 fa 和 dep 版本指针，从 root[latest] 换成 root[k]。后续所有 find 和新 union 都基于这个快照展开。

立即学习“C++免费学习笔记（深入）”；

• 初始化时调用 build(root[0], 1, n) 构建初始版本
• 每次 union 都生成新 root[i] 和新 dep_root[i]，用 modify 更新对应位置
• 查询操作如 opt == 3（判断连通性）时，直接在指定版本上调用 find(x) 和 find(y)，比较结果是否相等
• 注意：find 函数内部调用的是 query(root_ver, 1, n, x) 去取当前版本的 fa[x]，不是访问全局数组

最易被忽略的一点：dep 不是辅助信息，它是合并逻辑的决策依据，且必须和 fa 同步版本。漏掉 dep 的可持久化，或版本号没对齐，会导致合并方向错误，进而让 find 返回假根——整个结构就不可信了。