必须用按秩合并+可持久化数组（主席树）存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 都基于这个快照展开。
- 初始化时调用
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 返回假根——整个结构就不可信了。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
