判断两点连通性只需检查find_root(x) == find_root(y)，该函数通过access(x)、splay(x)后不断push_down并左跳至最浅深度节点实现，依赖中序遍历深度递增性质，漏push_down或误判is_root会导致错误。
怎么用 find_root 判断两个点是否连通
核心就一句话：find_root(x) == find_root(y) 成立，说明 x 和 y 在同一棵树里。这不是靠并查集，而是靠 LCT 自身结构实时维护的连通性。
find_root 的实现本质是：先 access(x) 把根到 x 的路径拉成实链，再 splay(x) 把 x 转到当前 Splay 根，然后一路往左子树跳（因为中序遍历深度递增，最左节点深度最小，就是原树的根）。过程中必须下放 rev 标记，否则左子树可能被翻转过，跳错方向。
常见错误现象：
- 没在跳左子树前调用
push_down，导致tr[x].s[0]实际是右子树，find_root返回错误节点 - 误以为
tr[x].p == 0就是根——LCT 中父指针只记录虚边关系，不能直接用 - 在未
access就直接splay后找左儿子，此时x所在 Splay 不一定包含原树根，结果无意义
link 和 cut 怎么保证连通性变更正确
link(x, y) 前必须确保 find_root(x) != find_root(y)，否则会成环；cut(x, y) 前必须确保 x 和 y 确实存在边（且是父子关系），否则非法删除。
立即学习“C++免费学习笔记（深入）”；
标准写法是：
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
-
link(x, y)：先makeroot(x)，再设tr[x].p = y。这样x成为新根，y是它唯一父节点，虚边变实边的逻辑由后续access触发 -
cut(x, y)：先makeroot(x)，再access(y)、splay(y)，此时若tr[y].s[0] == x且tr[x].p == y，才安全清空tr[x].p和tr[y].s[0]
漏掉 makeroot 是高频坑：比如直接 tr[x].p = y，但 x 原本有父节点，会导致父子关系错乱、虚实边混乱，find_root 随即失效。
为什么不能只靠 access + splay 就判断连通性
access(x) 只保证把 x 到其所在树**当前根**的路径变成实边，并不保证这个“当前根”就是整个连通块的原始根。LCT 中的“根”是动态的——makeroot 会切换根，而 access 本身不改变树的拓扑，只调整实边分布。
所以必须用 find_root，它强制把路径拉通、转上来、再往最左找，这个过程天然规避了“谁是根”的歧义。如果跳左子树时遇到空节点，说明当前 Splay 的根就是原树根；否则继续跳——这个逻辑依赖 Splay 中序深度严格递增的性质，一旦 push_down 漏掉或 rotate 写错，整条链的深度序就崩了。
性能上，find_root 均摊 O(log n)，但最坏单次 O(n)（退化链+未 splay），所以实际代码里别省那一次 splay(x)。
调试连通性问题时最该检查的三处
连通性出错，90% 都卡在这三个地方：
-
push_down是否覆盖了所有可能带rev标记的节点？尤其find_root循环体内部每次取tr[x].s[0]前，必须push_down(x) -
is_root(x)判断是否写成tr[x].p == 0？正确写法是tr[tr[x].p].s[0] != x && tr[tr[x].p].s[1] != x，否则虚边父子关系会被误判为实边 -
link/cut前是否做了连通性预检？比如cut对非邻接点操作，会静默破坏结构，后续find_root返回完全不可信的节点
真正麻烦的不是写错某个函数，而是多个操作叠加后标记残留、虚实边状态错位——这时候打印每个节点的 tr[x].p、tr[x].s[0/1] 和 tr[x].rev，比重读十遍论文更管用。
