路径压缩

一句话理解

路径压缩让节点直接连到根。

为什么要学

find 均摊近乎 O(1)。

讲解

压缩后树变扁。不要在需要保留树形态（如带权要小心顺序）时盲目写。

例子

链 1-2-3-4 第一次 find(4) 后大家都连到 1。

常见错误

• 边有权时路径压缩要顺带更新权。
• 压缩写成 fa[x]=fa[fa[x]] 只压一层也可以，但完全压缩更常见。