可回滚并查集

Rollback DSU 牺牲路径压缩，让每次 union 只改常数字段，并把旧值按时间顺序压栈。快照只是一个栈长度；递归分支退出时逆序恢复到该边界，便能共享父状态而让兄弟子问题彼此隔离。

递归搜索例子 ​

在分治递归节点加入一批当前区间有效的边，进入孩子前保存栈长；孩子处理完 rollback 到该长度。左右孩子因此共享父节点状态，却不会互相泄漏修改。这比复制整个 DSU 状态节省空间和时间。

易错边界 ​

重复 union 两个已连通顶点不改变结构，但快照语义必须一致：可压一个 no-op 标记，或只以栈长度回滚并确保调用方不按 union 次数撤销。路径压缩会修改整条路径，若不逐项记录就无法恢复。rollback 只能撤销栈顶历史；任意版本查询属于持久化，任意过去编辑属于追溯结构公理库追溯数据结构retroactive data structure · retroactivity允许在操作时间线的过去插入或删除更新，并重新解释其后状态的数据结构模型。。

可回滚摘要 ​

若每个分量还维护权重和、二分图 parity 或最小编号，union 时必须把所有被覆盖字段的旧值一并压栈。恢复顺序与写入相反，且只把小根挂到大根，保证 Find 最坏 $O(\log n)$。以分量和为例，合并前记录大根旧 sum，回滚后既恢复 parent/size，也恢复 sum；只撤父指针会留下跨分量污染。

历史栈空间与成功合并次数及附加字段数线性。深度优先分治中最大同时栈长通常为当前根叶路径所加入边数，而非所有递归节点边副本之和。

栈中究竟记录什么 ​

执行 union(a,b) 前先找两根 $r_a,r_b$。若相同，也要推入一个 no-op 标记，保证“调用次数快照”能一致回滚；若不同，令小树根挂到大树根，并把 (被挂根, 旧父亲, 新根, 旧大小) 推栈。恢复时按相反顺序写回，不能重新调用 union 猜测旧状态。

一次递归搜索的状态轨迹是：

1. snap = history.length；
2. 应用当前节点代表的所有边；
3. 递归访问子问题并回答叶查询；
4. rollback(snap)，逐项弹栈到原长度。

按大小合并使 find 最坏 $O(\log n)$，成功 union 改常数字段，回滚每条记录 $O(1)$。若额外维护连通分量数、二分图奇偶势或分量和，也必须把每个被改摘要的旧值纳入同一记录；否则父指针恢复了，查询语义仍留在未来状态。